學(xué)到了一種新的記錄最小元素下標(biāo)的方法。
題目：
給你一個(gè)字符串s戈稿。它可能包含任意數(shù)量的'*'字符西土。你的任務(wù)是刪除所有的'*'字符。
當(dāng)字符串還存在至少一個(gè)'*'字符時(shí)器瘪，你可以執(zhí)行以下操作：
刪除最左邊的'*'字符翠储，同時(shí)刪除該星號(hào)字符左邊一個(gè)字典序?最小的字符。如果有多個(gè)字典序最小的字符橡疼，你可以刪除它們中的任意一個(gè)援所。
請(qǐng)你返回刪除所有'*'字符以后，剩余字符連接而成的 字典序最小的字符串欣除。
示例 1：
輸入：s = "aaba*"
輸出："aab"
解釋：
刪除?'*'號(hào)和它左邊的其中一個(gè)'a'字符住拭。如果我們選擇刪除s[3]，s字典序最小历帚。
示例 2：
輸入：s = "abc"
輸出："abc"
解釋：
字符串中沒(méi)有'*'字符滔岳。
提示：
1 <= s.length <= 105
s只含有小寫英文字母和'*'字符。
輸入保證操作可以刪除所有的'*'字符挽牢。
思路：
這道題的本質(zhì)是每次遇到'*'時(shí)谱煤，都需要?jiǎng)h除目前為止所遇到的最小元素（當(dāng)有多個(gè)相同的最小元素時(shí)，應(yīng)當(dāng)刪除最晚出現(xiàn)的那一個(gè)）禽拔。最小堆可以記錄最小元素刘离，但是無(wú)法將其與元素在原字符串中的下標(biāo)一一對(duì)應(yīng)。
一種巧妙的利用列表下標(biāo)天然有序性的做法：創(chuàng)建26個(gè)列表睹栖，每個(gè)列表依次維護(hù)為'a','b','c'……的元素的下標(biāo)硫惕。添加下標(biāo)的過(guò)程無(wú)形之中保障了“最晚出現(xiàn)”的限制條件，而在遇到'*'時(shí)野来，找到第一個(gè)不為空的列表做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)))
