20201220
题目:
给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。
需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例:
- 示例 1:
输入:s = "bcabc"
输出:"abc"
- 示例 2:
输入:s = "cbacdcbc"
输出:"acdb"
提示:
- 1 <= s.length <=
- s 由小写英文字母组成
抛砖引玉
栈 stack(先进先出
s 中元素逐个入栈,如果遇到 Unicode 较小的元素,尽量将其放大栈底部 (如果后续还有栈内已经排列的原则,则出栈让 Unicode 较小的元素先入栈)
抛砖引玉
维护一个栈 stack(先进先出):
- 如果元素没有在栈中出现过:
- 如果栈内无元素,直接入栈
- 如果栈内有元素,且当前要入栈元素 Unicode 码小于栈底元素, 则栈底元素逐个出栈直到栈为空或者 Unicode 小于当前要入栈元素,如果当前要入栈元素入栈
- 因为栈内元素保持 Unicode 相对原字符位置递增(相对位置不变,保持 Unicode 栈底到栈顶递增), 则如果遇到已在栈内出现的元素,则忽略
/**
* @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 栏目 欢迎关注留言
公众号:前端小书童