316. 去除重复字母

Difficulty
Medium
Tags
单调栈
URL
https://leetcode-cn.com/problems/remove-duplicate-letters/
Star
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
示例 1：
输入：s = "bcabc"输出："abc"
示例 2：
输入：s = "cbacdcbc"输出："acdb"
提示：
  • 1 <= s.length <= 104
  • s 由小写英文字母组成

单调栈

思路
遍历字符，如果遇到栈顶的字符比当前字符大 且 栈顶字符会在当前字符后面再次出现，那么栈顶字符就可以直接删掉。这样最后栈内的元素就是最小的。
怎么判断栈顶元素是否会在当前字符后面再次出现呢？维护一个字典，存放每个字符最后出现的下标。
题解
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last = {}
        for i in range(len(s)):
            last[s[i]] = i
        stack = []
        for i in range(0, len(s)):
            if s[i] in stack:
                continue
            while stack and s[i] < stack[-1] and last[stack[-1]] > i:
                stack.pop()
            stack.append(s[i])
        return "".join(stack)