Leetcode 3170. Lexicographically Minimum String After Removing Stars

本文主要是介绍Leetcode 3170. Lexicographically Minimum String After Removing Stars，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 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。

这篇关于Leetcode 3170. Lexicographically Minimum String After Removing Stars的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---