【一天一大 lee】去除重复字母 (难度:中等) - Day20201220

2021-01-05 10:09:14 浏览数 (1)

20201220

题目:

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。

需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例:

  1. 示例 1:
代码语言:javascript复制
输入:s = "bcabc"
输出:"abc"
  1. 示例 2:
代码语言:javascript复制
输入:s = "cbacdcbc"
输出:"acdb"

提示:

  • 1 <= s.length <=
10^4
  • s 由小写英文字母组成

抛砖引玉

栈 stack(先进先出

s 中元素逐个入栈,如果遇到 Unicode 较小的元素,尽量将其放大栈底部 (如果后续还有栈内已经排列的原则,则出栈让 Unicode 较小的元素先入栈)

抛砖引玉

维护一个栈 stack(先进先出):

  • 如果元素没有在栈中出现过:
    • 如果栈内无元素,直接入栈
    • 如果栈内有元素,且当前要入栈元素 Unicode 码小于栈底元素, 则栈底元素逐个出栈直到栈为空或者 Unicode 小于当前要入栈元素,如果当前要入栈元素入栈
  • 因为栈内元素保持 Unicode 相对原字符位置递增(相对位置不变,保持 Unicode 栈底到栈顶递增), 则如果遇到已在栈内出现的元素,则忽略
代码语言:javascript复制
/**
 * @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 栏目 欢迎关注留言

公众号:前端小书童

0 人点赞