去除重复字母 图解题解

这道题到底在问什么

s

"cbacdcbc"

输出

"acdb"

含义

a,b,c,d 各留一个，且最小

先想最直接的笨办法

字母种类一多，排法就爆炸式增长，根本枚举不过来。我们需要一个一趟扫完就能定下顺序的聪明办法。（动画第 3 步）

最优解：一步一步想明白

1. 3字母种类一多，排法就爆炸式增长，根本枚举不过来。我们需要一个一趟扫完就能定下顺序的聪明办法。
2. 4关键两个条件缺一不可：① 栈顶比当前大(留着它会让串更大) ② 栈顶后面还会出现(弹了不亏，能补回)。两条都满足才敢弹。
3. 5下面演示串 cbacdcbc(下标 0~7)。先记住这张最后出现表：c 最后在 7、b 在 6、a 在 2、d 在 4。盯住栈怎么涨、怎么「反悔」。
4. 6指针未出发 · 栈空上面是输入流 cbacdcbc，下面是空栈。我们额外用一个集合记「栈里已经有哪些字母」，已在栈里的字母直接跳过(因为只能留一个)。
5. 7栈空 → 没有栈顶可比指针落在第一个 c(下标 0)。此刻栈还是空的，没有栈顶可比较，弹栈条件直接跳过，进入压栈。
6. 8压栈 → [c]把 c 压栈，栈变 [c]。
7. 9c > b 且 c 后面还出现(7>1)来了 b。栈顶 c 比 b 大，而且 c 的最后位置是 7、在 1 后面还会出现——两条都满足，c 可以先弹掉，把更小的 b 提前。
8. 10弹栈 → [] · c 以后再补弹掉 c，栈空了。不亏——c 在下标 3、5、7 还会回来，到时再压。这一步就是单调栈的「反悔」。
9. 11压栈 → [b]弹完后栈空，把 b 压栈，栈变 [b]。现在结果开头是更小的 b 而不是 c 了。
10. 12b > a 且 b 后面还出现(6>2)来了 a。栈顶 b 比 a 大，且 b 最后在 6、在 2 后面还会出现——可以弹，让最小的 a 排到最前。
11. 13弹栈 → [] · b 以后再补弹掉 b，栈又空了。b 在下标 6 还会回来，不怕丢。
12. 14压栈 → [a] · a 是最后一个把 a 压栈，栈变 [a]。注意 a 最后就出现在这里(下标 2)，往后永远不会再来——所以 a 一旦进栈，谁都别想再把它弹走。
13. 15a < c → 不弹来了 c。栈顶是 a，a 比 c 小，留着 a 不会让串变大，不弹。直接进入压栈。
14. 16压栈 → [a, c]c 不在栈里，压栈，栈变 [a, c]。这个 c 就是前面弹掉的 c「补回来」了。
15. 17c < d → 不弹来了 d。栈顶 c 比 d 小，不该弹，留着。准备压 d。
16. 18压栈 → [a, c, d]d 不在栈里，压栈，栈涨到 [a, c, d]，目前是升序、很「整齐」。
17. 19c 已在栈 → 跳过又来一个 c，但 c 已经在栈里了。每个字母只能留一个，所以直接跳过，栈不动。
18. 20d>b 但 d 后面不再出现(4<6)来了 b。栈顶 d 确实比 b 大，但 d 最后只出现在下标 4，已经在 6 前面了——弹了 d 就永远补不回来！第二个条件不满足，不能弹。
19. 21压栈 → [a, c, d, b]既然 d 不能弹，b 只好压在后面，栈变 [a, c, d, b]。这就是为什么结果末尾是 b——它没法再往前提了。
20. 22c 已在栈 → 跳过最后一个 c，栈里已经有 c，跳过，栈保持 [a, c, d, b]。
21. 23栈 [a, c, d, b] = 答案 acdb串走完了，栈从底到顶拼起来就是答案 acdb。每个字母只留一个、整串字典序最小，全靠那两条弹栈条件一趟扫出来。
22. 24整条 cbacdcbc 只从左扫到右一遍，没有任何回头——这就是单调栈把指数级压到 O(n) 的威力。
23. 27凡是「要让结果字典序/数值最优、且元素以后还可能再遇到」的题，第一反应就该想到单调栈 + 反悔。
24. 29i=6 b 来了，只因 d>b 就弹 d如果只看「d > b」就弹掉 d(不查它最后位置)，栈会变成 [a, c, b]。
25. 30扫完仍是 acb，缺了 d可 d 在下标 6 之后再也不出现，弹了就补不回来，最终错得到 acb(少了 d)。正确做法必须查 last[d]=4 < 6，不能弹 d。
26. 31abcabc 中后三个全跳过像 abcabc：前三个 a,b,c 升序压栈，后三个 a,b,c 全都已在栈里被跳过，结果就是 abc。没有任何弹栈。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def removeDuplicateLetters(self, s):
        last = {c: i for i, c in enumerate(s)}  # 每个字母最后位置
        stack = []
        seen = set()                  # 栈里已有哪些字母
        for i, c in enumerate(s):
            if c in seen:             # 已在栈里 → 跳过
                continue
            while stack and stack[-1] > c and last[stack[-1]] > i:
                seen.discard(stack.pop())   # 反悔：弹掉更大且后面还会来的
            stack.append(c)
            seen.add(c)
        return "".join(stack)

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> last(26, 0);
        for (int i = 0; i < (int)s.size(); i++) last[s[i]-'a'] = i;
        string stk;
        vector<bool> inStk(26, false);
        for (int i = 0; i < (int)s.size(); i++) {
            char c = s[i];
            if (inStk[c-'a']) continue;       // 已在栈 → 跳过
            while (!stk.empty() && stk.back() > c && last[stk.back()-'a'] > i) {
                inStk[stk.back()-'a'] = false;
                stk.pop_back();               // 反悔弹栈
            }
            stk.push_back(c); inStk[c-'a'] = true;
        }
        return stk;
    }
};

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i)-'a'] = i;
        StringBuilder stack = new StringBuilder();
        boolean[] inStack = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (inStack[c-'a']) continue;     // 已在栈 → 跳过
            while (stack.length() > 0 && stack.charAt(stack.length()-1) > c
                    && last[stack.charAt(stack.length()-1)-'a'] > i) {
                inStack[stack.charAt(stack.length()-1)-'a'] = false;
                stack.deleteCharAt(stack.length()-1);   // 反悔弹栈
            }
            stack.append(c); inStack[c-'a'] = true;
        }
        return stack.toString();
    }
}

复杂度

面试官可能追问