广州天河区网站建设公司,东莞网络游戏制作开发,域名大全免费查询,厦门同安网站建设题目#xff1a;去除重复字母
给你一个字符串 s #xff0c;请你去除字符串中重复的字母#xff0c;使得每个字母只出现一次。需保证 返回结果的字典序最小#xff08;要求不能打乱其他字符的相对位置#xff09;。
示例 1#xff1a;
输入#xff1a;s “bcabc” 输…题目去除重复字母
给你一个字符串 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();};
