题目描述
给了一个字符串s，需要删除重复的字符。
要求是（1）每个字母只保留一次；（2）结果的字典序最小
| f1-贪心+单调栈 |
基本分析
- 如果给定一个s，只能删除一个，怎么删可以使字典序最小？从左到右删除第一个s[i]>s[i+1]的值，比如456651，删除第二个6；987，删除9。
- 结合上面的思路，怎么能让字典序尽量的小？遍历字符串，用一个栈来进行维护，保证里面的字符单调递增
- 字符保留和单调递增有冲突，怎么维护？只剩一次的时候就不删了；之前出现过就pass。用vis记录栈中的元素访问情况；用cnt记录元素剩余的可用次数，pass掉或者弹出时，可用次数-1。
代码
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
vis = set()
cnt = Counter(s)
stk = []
n = len(s)
for i, ch in enumerate(s):
if ch in vis:
cnt[ch] -= 1
continue
while stk and s[stk[-1]] > ch:
if cnt[s[stk[-1]]] == 1:
break
else:
top = stk.pop()
vis.remove(s[top])
cnt[s[top]] -= 1
stk.append(i)
vis.add(ch)
return "".join([s[i] for i in stk])
总结
- 单调栈的两个特性，下标递增+下标对应的内容有某种规律
- 结果可以在栈中，也可以只把栈当工具，结果在数组中
- 有矛盾的约数的时候，其中一个只是限制条件