去除重复字母如何用贪心单调栈得到字典序最小结果？

简化版

去除重复字母要求每个字符出现一次且字典序最小。遍历字符串时，用栈维护结果；若当前字符比栈顶小，且栈顶后面还会出现，就弹出栈顶，让更小字符提前。用 visited 防止重复入栈，用剩余次数判断能不能弹。

详细版

先统计每个字符剩余次数。遍历字符 c 时先减少它的剩余次数；如果 c 已经在栈中，跳过。否则，当栈顶字符大于 c 且栈顶后面还会出现时，弹出栈顶并标记未访问。最后把 c 入栈。

这个贪心保证了：能让字典序变小的字符尽量提前，同时不会丢失必须出现的字符。时间复杂度 O(n)，空间复杂度 O(字符集大小)。

完整版教学

一、题目有两个约束，不能只看字典序

结果要满足：

1. 每种字符只出现一次
2. 在所有合法结果中字典序最小

比如 s="bcabc"，答案是 "abc"。如果只按最小字符贪心，可能会漏掉必须保留的字符；如果只去重保持原顺序，可能得到 "bca"，字典序不最小。

二、为什么需要知道字符后面还会不会出现

当栈顶字符比当前字符大时，弹出栈顶能让字典序变小。但只有在栈顶字符后面还会出现时，才能放心弹；否则弹了就再也补不回来，结果缺字符。

条件	是否能弹栈顶
栈顶后面还会出现	可以弹，之后补回来
栈顶后面不会出现	不能弹，否则缺字符

记忆钩子：字典序想变小可以弹，但“后面还能补回来”才有资格弹。

这就是剩余次数 count 的意义。

三、单调栈维护什么

栈维护当前构造的最优结果前缀。遍历当前字符 c 时：

如果 c 已在栈中：跳过
否则 while 栈顶 > c 且 栈顶剩余次数 > 0：
    弹出栈顶
把 c 入栈

这看起来像单调递增栈，但不是绝对递增，因为有些大字符如果后面不再出现，就必须保留。

s = cbacdcbc
最终结果：acdb

d 虽然大，但后面没有第二个 d 时不能弹掉。

四、visited 为什么不可少

每个字符只能出现一次。即使某个字符很小，如果它已经在栈中，再遇到它也不能重复加入。

s = abac
读到第二个 a 时，a 已在栈中，跳过

visited[c] 表示字符是否已经在当前栈里。弹出字符时要把它改回 false，否则后面无法重新加入。

五、代码模板

String removeDuplicateLetters(String s) {
    int[] count = new int[26];
    boolean[] visited = new boolean[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        int idx = c - 'a';
        count[idx]--;
        if (visited[idx]) continue;
        while (!stack.isEmpty()
            && stack.peekLast() > c
            && count[stack.peekLast() - 'a'] > 0) {
            visited[stack.pollLast() - 'a'] = false;
        }
        stack.addLast(c);
        visited[idx] = true;
    }
    StringBuilder sb = new StringBuilder();
    for (char c : stack) sb.append(c);
    return sb.toString();
}

这份代码的三个结构分别负责：count 判断能不能弹，visited 防重复，stack 构造答案。

六、用例子推演

s="bcabc"：

读 b：栈 [b]
读 c：栈 [b,c]
读 a：a 更小，c 后面还有，弹 c；b 后面还有，弹 b；入 a
读 b：栈 [a,b]
读 c：栈 [a,b,c]

答案 "abc"。如果没有“后面还有”的判断，可能会弹掉无法补回的字符。

七、常见误区与追问

误区：只要栈顶大于当前字符就弹。 栈顶后面不再出现时不能弹。
误区：忘记 visited。 会让结果里出现重复字符。
误区：弹出后不更新 visited。 后续遇到该字符会被错误跳过。
追问：为什么这是贪心？ 每次在不破坏可行性的前提下，让当前前缀字典序尽量小。
追问：和移掉 K 位数字有什么像？ 都是单调栈贪心，但本题多了“必须保留每种字符一次”的约束。
追问：复杂度为什么是 O(n)？ 每个字符最多入栈一次、出栈一次。

八、加强记忆

去除重复字母要同时守住“字典序小”和“字符不能丢”。当前字符更小时，可以弹更大的栈顶，但前提是栈顶后面还能再出现。count 管能不能补，visited 管有没有重复，stack 管当前答案。三者缺一个，这题都容易翻车。

简化版

详细版