[316] 去除重复字母

details

解题思路

为了保证字典序最小并且去重，我们可以使用贪心 + 单调栈来解决这个问题。核心思路如下：

  1. 贪心策略：我们想要尽可能保持字母的相对顺序，并且选择字典序小的字母优先出现在前面。
  2. 栈的使用：利用栈存储最终要保留的字符，确保栈中的字符保持字典序递增。
  3. 去重：我们需要确保每个字符只出现一次，因此使用一个布尔数组来记录字符是否在栈中。
  4. 维护后续字符的可用性：我们需要记录每个字符在字符串中最后一次出现的位置，以便在遇到当前字符时，判断它是否还能出现在后续的字符中。

算法步骤：

  1. 遍历字符串，对每个字符进行判断：
    • 如果当前字符已经在栈中，则跳过。
    • 如果当前字符小于栈顶字符，且栈顶字符在后续还有出现，则可以将栈顶字符弹出，以确保字典序最小。
  2. 将当前字符压入栈，并标记该字符已经使用。
  3. 最终栈中的字符就是去重后的、且字典序最小的结果。

JavaScript 实现

var removeDuplicateLetters = function (s) {
    const size = s.length;
    let stack = [];

    let lastIndexArr = new Array(size).fill(0);
    for (let index = 0; index < size; index++) {
        lastIndexArr[s[index].charCodeAt(0) - 97] = index;
    }

    const set = new Set();
    for (let i = 0; i < size; i++) {
        const offset = s[i].charCodeAt(0) - 97;

        if (set.has(offset)) continue;
        while (stack.length && stack.at(-1).charCodeAt(0) > s[i].charCodeAt(0) && lastIndexArr[stack.at(-1).charCodeAt(0) - 97] > i) {
            set.delete(stack.pop()?.charCodeAt(0) - 97);
        }
        set.add(offset);
        stack.push(s[i]);
    }
    return stack.join('');
};

复杂度分析

  • 时间复杂度: O(n)，其中 n 是字符串的长度。我们只遍历字符串一次，且每个字符最多入栈和出栈各一次。
  • 空间复杂度: O(1)，由于只使用了常数级别的辅助数组来记录字符信息（长度为 26 的固定数组）。
Last Updated:
Contributors: rosendo