去除重复字母【hard】

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
来源：https://leetcode.cn/problems/remove-duplicate-letters/

去掉一部分，使得字典序最大（最小），是一种很著名的单调栈题型。
其解法相对较为固定的部分是：保证单调栈是单调增加的。如果不单调增，则要删掉栈顶的那个“太大”的元素（往往有一定条件）
在本题中，其条件为：该字符在后面至少还有一次出现（否则就删没了）
此外，还需要考虑删除少了的情况。在本题中的方法为：如果前面已经出现过了这个元素，那么无条件删除后续要加进去的元素（相当于做了从后往前的删除）。有些时候，也可能是诸如“直接截断出前xxx个元素”

有一个对这类题型的很好归纳，见：https://leetcode.cn/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/

此外，有一点python上的技巧，例如末尾数组用stack[-1]。

```python
from functools import reduce
from operator import add

class Solution:
    # //去掉一部分，使得字典序最大（最小），是一种很著名的单调栈题型。
    # //其解法相对较为固定的部分是：保证单调栈是单调增加的。如果不单调增，则要删掉栈顶的那个“太大”的元素（往往有一定条件）
    # //在本题中，其条件为：该字符在后面至少还有一次出现（否则就删没了）
    # //此外，还需要考虑删除少了的情况。方法为：如果前面已经出现过了这个元素，那么无条件删除后续要加进去的元素（相当于做了从后往前的删除）
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        hasadd = set()
        ccount = {}  # 到了当前位置后，“后面”还剩下的该元素的个数
        # 开始遍历s中的每个元素
        for c in s:
            ccount.setdefault(c, 0)
            ccount[c] += 1
        for c in s:
            if c not in hasadd:
                while len(stack) > 0 and stack[-1] > c and ccount[stack[-1]] != 0:
                    hasadd.remove(stack[-1])
                    stack.pop()
                    # 将这个元素添加进入:
                stack.append(c)
                hasadd.add(c)
            ccount[c] -= 1  # 老是在这里忘了
        return reduce(add, stack)

s = Solution()
print(s.removeDuplicateLetters("bcabc"))
```

Alangy's Blog

导航

近期文章

友情链接