LeetCode 316. 去除重复字母

约 6 分钟
文章信息 14 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 腾讯 字节 阿里 华为 美团 京东 百度 网易 猿辅导
标签
字符串 栈 贪心 单调栈

题目描述

✅ 316. 去除重复字母

image-20260928203255596

题意分析

从字符串中删除部分字符，使原串出现过的每种字母恰好保留一次，并让最终字符串的字典序最小。保留下来的字符必须维持原来的先后顺序，因此结果是原串的子序列，不能先排序再去重。

所有合法结果都包含同样的字母种类，长度相同。字典序由第一个不同位置的字符决定，所以需要在仍能保留全部字母的前提下，尽量让较小字符靠前。

解法：单调栈 + 剩余频次

核心思路

[!blue]

从左到右扫描，用栈保存当前选出的子序列。更小的新字母到来时，可以考虑撤销栈尾较大的字母，让新字母出现在更靠前的位置；但撤销的字母仍必须在后面出现，否则结果会永久缺少这一种字母。

先统计各字母总次数。扫描当前字符时先将对应 remain 减一，使它准确表示当前位置之后的剩余次数；used 则表示这个字母是否已在栈内。已经选过的字母不再入栈，但这次出现仍必须从剩余次数中扣除。

对尚未选入的当前字母，只有栈顶比它大且后面还有栈顶字母时，才允许弹出。弹出后清除那个字母的 used，使其后续副本能够重新进入。持续检查新栈顶，直到前面的字符不值得撤销，或者再撤销就无法补全字母种类。

这个贪心选择同时满足两个条件：用更小字母提前，改善了结果最早发生变化的位置；被推迟的字母仍可从后面补回，不破坏可完成性。扫描顺序和只撤销栈尾的操作保证结果始终是原串子序列。若较大栈顶已无后续副本，它就必须留下，因此最终栈不一定整体递增。

最后所有字母都被至少一次尝试加入，used 防止重复，remain 防止某类字母彻底丢失，栈中的字符串就是字典序最小的合法选择。

解题步骤

  1. 统计小写字母总次数到 remain，初始化 used 和空栈。
  2. 读取当前字母，先减少它的剩余次数；若它已经在栈中，跳过本次加入。
  3. 栈非空时，检查栈顶是否更大且以后还能出现；满足则弹出，并将其 used 设为假，继续检查。
  4. 将当前字母入栈，标记为已使用。
  5. 扫描结束后，按栈中从底到顶的顺序返回字符串。

代码实现

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] remain = new int[26];

        for (int i = 0; i < s.length(); i++) {
            remain[s.charAt(i) - 'a']++;
        }

        boolean[] used = new boolean[26];
        StringBuilder stack = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int index = ch - 'a';

            remain[index]--;

            if (used[index]) {
                continue;
            }

            while (stack.length() > 0) {
                char top = stack.charAt(stack.length() - 1);

                // 只有栈顶更大且后面还能补回它，才允许用当前较小字符替换。
                if (top <= ch || remain[top - 'a'] == 0) {
                    break;
                }

                // 弹出后撤销在栈标记，之后再次遇到该字符才能重新加入。
                used[top - 'a'] = false;
                stack.deleteCharAt(stack.length() - 1);
            }

            stack.append(ch);
            used[index] = true;
        }

        return stack.toString();
    }
}

func removeDuplicateLetters(s string) string {
    remain := make([]int, 26)
    for i := range s {
        remain[s[i]-'a']++
    }

    used := make([]bool, 26)
    stack := make([]byte, 0, 26)
    for i := range s {
        ch := s[i]
        index := ch - 'a'
        remain[index]--

        if used[index] {
            continue
        }
        for len(stack) > 0 {
            top := stack[len(stack)-1]
            // 只有栈顶更大且后面还能补回它，才允许用当前较小字符替换。
            if top <= ch || remain[top-'a'] == 0 {
                break
            }
            // 弹出后撤销在栈标记，之后再次遇到该字符才能重新加入。
            used[top-'a'] = false
            stack = stack[:len(stack)-1]
        }

        stack = append(stack, ch)
        used[index] = true
    }
    return string(stack)
}

复杂度分析

  • 时间复杂度：$O(n)$。统计和扫描各一遍，每个字符出现位置至多入栈一次、弹出一次，所有弹栈操作合计为线性数量。
  • 空间复杂度：$O(1)$。输入仅有 26 种小写字母，频次、使用标记和最多含 26 个字母的栈都不随字符串长度增长。

关键点总结

[!green]

  • 字典序优先改善靠前位置，但每次撤销都要保留完成全部字母覆盖的可能。
  • remain 管未来还能否补回，used 管当前是否已经选入，两者互相配合。
  • 弹出栈尾不会打乱已有子序列顺序；后续再遇到对应字母时可以重新选择。
  • 这里的栈带有可补回条件，不能把它误解为必须全局严格递增的栈。

易错点总结

[!yellow]

  • 只比较字符大小，不检查未来次数，会删除某类字母的最后一次可用出现。
  • 跳过已使用字母后才减少 remain，被跳过的出现次数没有消费，后面就可能误判还能补回。
  • 弹栈后不清除 used，被撤销字母的后续出现仍会被拒绝，结果缺少字母。
  • 只弹一次就停止，可能留下多个可以被当前较小字母推迟的栈尾字符。
  • 对原串排序后直接去重，虽然字母齐全，却不一定是原串的合法子序列。
  • 要求最终结果严格递增，忽略了原串顺序和最后出现位置对选择的限制。

相似题目

题目 难度 关联与区别
402. 移掉 K 位数字 中等 同样在更优字符出现时尝试弹栈，本题还要求被弹字符后面能补回且每种保留一次。
321. 拼接最大数 困难 同样用单调栈选字典序最优子序列，原题限制选择长度，本题限制字符覆盖种类。
1081. 不同字符的最小子序列 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题每种字符保留一次并追踪剩余次数，该题选择每种不同字符一次的最小字典序子序列。
1673. 找出最具竞争力的子序列 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题每种字符保留一次并追踪剩余次数，该题保留固定长度的最具竞争力子序列。
补充题 166. 去除重复字母的最大字典序子序列 中等 都用单调栈和剩余次数保证每种字母只留一次；补充题反转字典序比较方向。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/78861367
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！