学到了一种新的记录最小元素下标的方法。

题目：

给你一个字符串s。它可能包含任意数量的'*'字符。你的任务是删除所有的'*'字符。

当字符串还存在至少一个'*'字符时，你可以执行以下操作：

删除最左边的'*'字符，同时删除该星号字符左边一个字典序 最小的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。

请你返回删除所有'*'字符以后，剩余字符连接而成的 字典序最小的字符串。

示例 1：

输入：s = "aaba*"

输出："aab"

解释：

删除 '*'号和它左边的其中一个'a'字符。如果我们选择删除s[3]，s字典序最小。

示例 2：

输入：s = "abc"

输出："abc"

解释：

字符串中没有'*'字符。

提示：

1 <= s.length <= 105

s只含有小写英文字母和'*'字符。

输入保证操作可以删除所有的'*'字符。

思路：

这道题的本质是每次遇到'*'时，都需要删除目前为止所遇到的最小元素（当有多个相同的最小元素时，应当删除最晚出现的那一个）。最小堆可以记录最小元素，但是无法将其与元素在原字符串中的下标一一对应。

一种巧妙的利用列表下标天然有序性的做法：创建26个列表，每个列表依次维护为'a','b','c'……的元素的下标。添加下标的过程无形之中保障了“最晚出现”的限制条件，而在遇到'*'时，找到第一个不为空的列表做pop操作又保障了“最小”的限制条件。

代码如下：

class Solution(object):

    def clearStars(self, s):

        """

        :type s: str

        :rtype: str

        """

        st = [[] for _ in range(26)]

        for i, c in enumerate(s):

            if c != '*':

                st[ord(c) - ord('a')].append(i)

                continue

            for p in st:

                if p:

                    p.pop()

                    break

        return ''.join(s[i] for i in sorted(chain.from_iterable(st)))