【LeetCode每日一题】单调栈316去除重复字母

本文主要是介绍【LeetCode每日一题】单调栈316去除重复字母，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：去除重复字母

给你一个字符串 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('');};