1081. 不同字符的最小子序列
1081. 不同字符的最小子序列
🟠 🔖 栈
贪心
字符串
单调栈
🔗 力扣
LeetCode
题目
Given a string s
, return the lexicographically smallest subsequenceof s
that contains all the distinct characters of s
exactly once.
Example 1:
Input: s = "bcabc"
Output: "abc"
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
Constraints:
1 <= s.length <= 1000
s
consists of lowercase English letters.
Note: This question is the same as 316
题目大意
给你一个字符串 s
,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
比如说输入字符串 s = "babc"
,去重且符合相对位置的字符串有两个,分别是 "bac"
和 "abc"
,但是我们的算法得返回 "abc"
,因为它的字典序更小。
解题思路
哈希表 + 单调栈
题目有三个要求:去重、不能打乱其他字符顺序、字典序最小。
- 去重:可以通过 「使用哈希表存储字母出现次数」 的方式,将每个字母出现的次数统计起来,再遍历一遍,去除重复的字母。
- 不能打乱其他字符顺序:按顺序遍历,将非重复的字母存储到答案数组或者栈中,最后再拼接起来,就能保证不打乱其他字符顺序。
- 字典序最小:意味着字典序小的字母应该尽可能放在前面。
- 对于第
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]
之前出现的非重复、并且字典序最小的字符序列。整个算法步骤如下:
- 先遍历一遍字符串,用哈希表
count
统计出每个字母出现的次数。 - 然后使用单调递减栈保存当前字符之前出现的非重复、并且字典序最小的字符序列。
- 当遍历到
s[i]
时,如果s[i]
没有在栈中出现过(使用哈希表inStack
标记):- 比较
s[i]
和栈顶元素的字典序。如果s[i]
的字典序小于栈顶元素,并且栈顶元素之后的出现次数大于0
,则将栈顶元素弹出。 - 然后继续判断
s[i]
和栈顶元素,直到栈顶元素出现次数为0
时停止弹出。此时将s[i]
添加到单调栈中。
- 比较
- 从哈希表
count
中减去s[i]
出现的次数,继续遍历。 - 最后将单调栈中的字符依次拼接为答案字符串,并返回。
代码
/**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function (s) {
let count = new Map();
let inStack = new Map();
let stack = [];
for (let i of s) {
let val = count.get(i) || 0;
count.set(i, val + 1);
}
for (let i of s) {
count.set(i, count.get(i) - 1);
if (!inStack.get(i)) {
let top = stack[stack.length - 1];
while (top && i < top && count.has(top) && count.get(top) > 0) {
stack.pop();
inStack.set(top, false);
top = stack[stack.length - 1];
}
stack.push(i);
inStack.set(i, true);
}
}
return stack.join('');
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
1673 | 找出最具竞争力的子序列 | 栈 贪心 数组 1+ |