316. Remove Duplicate Letters

Leetcode link

题目简介

/**
 * @param {string} s
 * @return {string}
 */

题目给我们一个字符串，要求我们：

1. 去除所有重复元素
2. 在所有可能的剩余元素组合中，返回字典序最小的字符串

解题思路

根据题意，这题的重点在于：如何在正确的地方删除元素

我们要让最后字符串字典序最小，关键在于：我们把字典序小的字符往前放

这题的解题思路分成四步：

1. 我们需要拿到所有字符最后出现的下标（这样才知道我们后面还能不能拿到这个字符）
2. 创建一个单调栈，使其满足：字典序越来愈大
3. 遍历字符串 s，维护单调栈
4. 把单调栈转换成字符串返回

关键在于第三步，维护单调栈，我们需要在这个时候把符合以下条件的字符删除：

1. 当前遍历字符字典序小于栈顶元素
2. 栈顶元素后面还会出现

Javascript

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
    const len = s.length
    const lastOccurrence = {}

    for (let i = 0; i < len; i++) {
        lastOccurrence[s[i]] = i
    }

    const stack = []
    const visited = new Set()

    for (let i = 0; i < len; i++) {
        if (visited.has(s[i])) {
            continue
        }

        while (stack.length > 0 && s[i] < stack[stack.length - 1] && i < lastOccurrence[stack[stack.length - 1]]) {
            visited.delete(stack.pop())
        }

        stack.push(s[i])
        visited.add(s[i])
    }
    return stack.join('')
};

复杂度分析

时间

O(n)

空间

O(1)

lastOccurrence，stack，visited 这仨受限于小写字符的数量，长度最多只可能有 26，所以是 1