20201220
给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。
需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
输入:s = "bcabc"
输出:"abc"
输入:s = "cbacdcbc"
输出:"acdb"
提示:
栈 stack(先进先出
s 中元素逐个入栈,如果遇到 Unicode 较小的元素,尽量将其放大栈底部 (如果后续还有栈内已经排列的原则,则出栈让 Unicode 较小的元素先入栈)
抛砖引玉
维护一个栈 stack(先进先出):
/**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function(s) {
const map = new Map(),
stack = [],
stackMap = new Map()
// 对s中元素计数
for (let c of s) {
map.set(c, (map.get(c) || 0) + 1)
}
for (let c of s) {
if (!stackMap.has(c)) {
// 从栈底清除Unicode大于要入栈元素
while (stack.length > 0 && stack[stack.length - 1] > c) {
// 出栈前保证本次出栈的原则,在后面还会出现
if (map.get(stack[stack.length - 1]) > 0) {
stackMap.delete(stack[stack.length - 1])
stack.pop()
} else {
break
}
}
// 入栈
stackMap.set(c)
stack.push(c)
}
// 更新未处理元素数量
map.set(c, (map.get(c) || 0) - 1)
}
return stack.join('')
}
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童