题目:去除重复字母
给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:
输入:s = “bcabc”
输出:“abc”
示例 2:
输入:s = “cbacdcbc”
输出:“acdb”
其实这道题我觉得和 402. 移掉 K 位数字很像的,这道题的题解可以看一下单调栈的总结与案例复盘。
思路:
402 是构造单调递增栈的过程中,通过k的数量判断要不要将栈顶元素弹出。
316 是构造单调递增栈的过程中,通过 尚未遍历的元素中(restMap
)是否还有和栈顶元素重复的元素,如果没有了,那么栈顶元素不可以去除,否则可以去除。
316 还需要判断一下栈内(usedMap
)是否有这个元素,如果已经有了,也不可以入栈。
316 中需要用两个map来维护栈内的元素个数 和 尚未遍历的元素个数。
var removeDuplicateLetters = function(s) {
let restMap = new Map();
let usedMap = new Map();
for(let i = 0; i < s.length; i++){
if(!restMap.has(s[i])){
restMap.set(s[i],0);
}
restMap.set(s[i],restMap.get(s[i])+1);
usedMap.set(s[i], 0);
}
let stack = [];
for(let i = 0; i < s.length; i++){
restMap.set(s[i],restMap.get(s[i])-1);
// 如果栈里已经有了就不要再入栈了,比如栈里有ab,如果当前元素是a,
// 那么a就会将b弹出,不会弹出a,又因为栈里已经有a,所以当前元素也不会将元素压入栈中,
// 因此无缘无故弹出一个元素,我们一定要清楚,弹出元素是为了不破坏单调性,不弹也不会破环。
if(usedMap.get(s[i]) === 1){
continue;
}
//构造单调递增
while(stack.length && s[i] < stack[stack.length-1] && restMap.get(stack[stack.length-1]) > 0){
let top = stack.pop();
usedMap.set(top,0);
}
// 栈里没有才能往里面放
stack.push(s[i]);
usedMap.set(s[i],1);
}
return stack.join('');
};