难度: Medium
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"输出："abc"
示例 2：
输入：s = "cbacdcbc"输出："acdb"
提示：
1 <= s.length <= 104s 由小写英文字母组成注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
运行时间: 24 ms
内存: 0.0 MB
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
stack = []
instack = defaultdict(int)
cnt = defaultdict(int)
for c in s:
cnt[c] += 1
for c in s:
cnt[c] -= 1
if instack[c]:
continue
while stack and stack[-1] > c and cnt[stack[-1]]:
p = stack.pop()
instack[p] -= 1
stack.append(c)
instack[c] += 1
return ''.join(stack)
该题解使用了单调栈的思路。具体来说，遍历字符串 s 中的每个字符，如果当前字符已经在栈中，则直接跳过；否则，将栈顶元素与当前字符比较，如果栈顶元素大于当前字符且栈顶元素在后面还会出现，则弹出栈顶元素，直到栈为空或栈顶元素小于等于当前字符。然后将当前字符压入栈中。最后将栈中元素拼接成字符串作为结果返回。这样可以保证结果字符串的字典序最小。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
stack = []
instack = defaultdict(int) # 记录字符是否在栈中
cnt = defaultdict(int) # 记录字符的剩余出现次数
# 统计每个字符的出现次数
for c in s:
cnt[c] += 1
for c in s:
cnt[c] -= 1 # 更新字符的剩余出现次数
if instack[c]: # 如果字符已经在栈中，跳过
continue
# 如果栈顶元素大于当前字符且在后面还会出现，弹出栈顶元素
while stack and stack[-1] > c and cnt[stack[-1]]:
p = stack.pop()
instack[p] -= 1
stack.append(c) # 将当前字符压入栈中
instack[c] += 1
return ''.join(stack) # 将栈中元素拼接成字符串作为结果返回
单调栈通过维持栈中元素的单调递增顺序来确保生成的字符串具有最小的字典序。在处理每个字符时，如果发现栈顶元素大于当前字符且栈顶元素在后面的字符串中还会再次出现，就将栈顶元素弹出。这样做可以保证在不破坏结果字符串中字符的唯一性的前提下，每次都尽可能用较小的字符替代较大的字符，从而使得最终形成的字符串字典序最小。
如果输入字符串`s`包含所有26个英文字母，则单调栈的最大可能高度是26。这种情况发生在字符串`s`已经按照某种字典序排列，且每个字符至少出现一次时，单调栈将可能包含所有这些字符，因为没有任何字符需要被弹出栈以保持字典序最小。
跳过栈中已有的字符是基于逻辑：一旦一个字符被加入到栈中，它就会出现在最终的结果字符串中，因为每个字符在结果中只能出现一次。通过使用`instack`哈希表来记录哪些字符已在栈中，可以确保不会重复处理这些字符。这样做是为了维持每个字符在结果字符串中的唯一性，避免重复添加导致的错误。
通过`cnt`哈希表来跟踪每个字符在遍历过程中的剩余出现次数，可以决定是否可以安全地弹出栈顶元素。在每次遍历到一个字符时，会将其在`cnt`表中的计数减一。如果栈顶元素的计数大于0，表示该字符在字符串的后续部分还会再次出现，因此可以将其从栈中弹出以保持最小字典序。若计数为0，则表示栈顶元素不会再出现，不能弹出，以确保字符的出现至少一次。