1081. 不同字符的最小子序列 #
- 标签:栈、贪心、字符串、单调栈
- 难度:中等
题目大意 #
给定一个字符串 s
。
要求:返回 s
字典序最小的子序列,该子序列包含 s
的所有不同字符,且只包含一次。
解题思路 #
针对题目的两个要求:包含所有不同字符,且只包含一次(去重)、子序列(不能打乱其他字符顺序)、字典序最小。我们来一一进行分析。
- 包含所有不同字符,且只包含一次(去重):可以通过 「使用哈希表存储字母出现次数」 的方式,将每个字母出现的次数统计起来,再遍历一遍,去除重复的字母。
- 子序列(不能打乱其他字符顺序):按顺序遍历,将非重复的字母存储到答案数组或者栈中,最后再拼接起来,就能保证不打乱其他字符顺序。
- 字典序最小:意味着字典序小的字母应该尽可能放在前面。
- 对于第
i
个字符s[i]
而言,如果第0
~i - 1
之间的某个字符s[j]
在s[i]
之后不再出现了,那么s[j]
必须放到s[i]
之前。 - 而如果
s[j]
在之后还会出现,并且s[j]
的字典序大于s[i]
,我们则可以先舍弃s[j]
,把s[i]
尽可能的放到前面。后边再考虑使用s[j]
所对应的字符。
- 对于第
要满足第 3 条需求,我们可以使用 「单调栈」 来解决。我们使用单调栈存储 s[i]
之前出现的非重复、并且字典序最小的字符序列。整个算法步骤如下:
-
先遍历一遍字符串,用哈希表
letter_counts
统计出每个字母出现的次数。 -
然后使用单调递减栈保存当前字符之前出现的非重复、并且字典序最小的字符序列。
-
当遍历到
s[i]
时,如果s[i]
没有在栈中出现过:- 则比较
s[i]
和栈顶元素stack[-1]
的字典序。如果s[i]
的字典序小于栈顶元素stack[-1]
,并且栈顶元素之后的出现次数大于0
,则将栈顶元素弹出。 - 然后继续判断
s[i]
和栈顶元素stack[-1]
,并且知道栈顶元素出现次数为0
时停止弹出。此时将s[i]
添加到单调栈中。
- 则比较
-
从哈希表
letter_counts
中减去s[i]
出现的次数,继续遍历。 -
最后将单调栈中的字符依次拼接为答案字符串,并返回。
代码 #
|
|