• Leetcode 3170. Lexicographically Minimum String After Removing Stars
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3170. Lexicographically Minimum String After Removing Stars

1. 解題思路

這一題的話只需要維護一個有序數列（這里我們用堆排來處理），然后每當遇到一個*時，就從有序數列當中彈出最小的元素即可。

需要注意的是，由于需要獲取字母排序最小的答案，因此，我們應該遵循如下排序規則：

• 字母序小的字母排前面
• 相同字母出現靠后的排前面

2. 代碼實現

給出python代碼實現如下：

class Solution:def clearStars(self, s: str) -> str:q = []deleted = set()for i, ch in enumerate(s):if ch == "*":out = heapq.heappop(q)idx = -out[1]deleted.add(idx)else:heapq.heappush(q, (ch, -i))ans = ""for i, ch in enumerate(s):if ch != "*" and i not in deleted:ans += chreturn ans

提交代碼評測得到：耗時669ms，占用內存29.4MB。