去除重复字母

---

image.png

要求一、要去重。

要求二、去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序。

要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。

有序需要依赖单调栈，最佳的情况是小的放前面打的放后面，这可以依赖单调栈，但是如果大的在pop之后后继无人的话还是得保留，所以作为特例处理（此时为最大数的最低位所以还是最优解）。

• 记住先判断是否已选，已选之后才是while...pop

res计算i位之后的各个字符出现的次数，choose记录栈里面已经选了哪些字符。对于已选字符不入栈但是要修改res。

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        if s=="":
            return s
        # 剩余计数器
        res={}
        # 已选记录
        choose={}
        for i in s:
            if i in res:
                res[i]+=1
            else:
                res[i]=1
            choose[i]=0
        stack=[s[0]]
        res[s[0]]-=1
        choose[s[0]]=1
        for i in range(1,len(s)):
            res[s[i]]-=1
            if s[i] not in stack:
                while len(stack)>0 and ((stack[-1]>s[i] and res[stack[-1]]>0)):
                    t=stack.pop()
                    choose[t]=0
                if choose[s[i]]==0:
                    stack.append(s[i])
                    choose[s[i]]=1
        return "".join(stack)