删除字符串中的所有相邻重复项 图解题解

这道题到底在问什么

s

"abbaca"

输出

"ca"

过程

abbaca → aaca → ca

最优解：一步一步想明白

1. 3能做对，但每删一次就要重头再扫。像 aaaa… 这种，每趟只消掉一点，最坏要扫很多趟 → O(n²)。重复扫描就是慢的根源。
2. 4栈就是为「最近一个还没了结的」而生：和栈顶相同就 弹栈(消一对)，否则压栈。从左到右扫一遍，连锁反应被栈自动接住，你不用回头。
3. 5栈为空，指针还没出发换条更长的串 cabccbaddxyyxez 把过程演透——它里头藏了两段连锁消除。上面是输入流，下面是空栈。指针从左到右逐字符扫，盯住栈怎么涨怎么消。
4. 6压栈 → [c]第 1 个字符 c，栈是空的，没人能和它配对，压栈，栈变 [c]。
5. 7压栈 → [c, a]第 2 个是 a，栈顶是 c，不一样，消不掉，压栈，栈变 [c, a]。
6. 8压栈 → [c, a, b]第 3 个是 b，栈顶是 a，不同，继续压栈，栈一路涨到 [c, a, b]。
7. 9压栈 → [c, a, b, c]第 4 个又是 c，栈顶是 b，不同，压栈，栈涨到 [c, a, b, c]——注意这串 cabc 一个都没消，全堆着。
8. 10弹栈(消一对) → [c, a, b]第 5 个是 c，栈顶正好也是 c——凑成一对！弹栈消掉，栈回到 [c, a, b]。消完后新露出的栈顶是 b，连锁就要开始了。
9. 11弹栈(消一对) → [c, a]第 6 个是 b，和刚露出的栈顶 b 又凑一对！弹栈消掉，栈剩 [c, a]，新栈顶变成 a。
10. 12弹栈(消一对) → [c]第 7 个是 a，又和栈顶 a 配对，再弹栈——一口气消了三对 cc、bb、aa！栈塌回 [c]。这就是栈替你自动接住的连锁反应。
11. 13压栈 → [c, d]第 8 个是 d，栈顶是 c，不同，压栈，栈变 [c, d]。
12. 14弹栈(消一对) → [c]第 9 个又是 d，和栈顶 d 配对，弹栈消掉，栈回到 [c]。
13. 15压栈 → [c, x]第 10 个是 x，栈顶是 c，不同，压栈，栈变 [c, x]——第二段连锁正在埋伏笔。
14. 16压栈 → [c, x, y]第 11 个是 y，栈顶是 x，不同，压栈，栈涨到 [c, x, y]。
15. 17弹栈(消一对) → [c, x]第 12 个又是 y，和栈顶 y 配对，弹栈消掉，栈剩 [c, x]——新栈顶 x 露出来了。
16. 18弹栈(消一对) → [c]第 13 个是 x，消掉 yy 后新露出的栈顶正好是 x——再凑一对！弹栈，栈又塌回 [c]。第二段连锁也被栈接住了。
17. 19压栈 → [c, e]第 14 个是 e，栈顶是 c，不同，压栈，栈变 [c, e]。
18. 20压栈 → [c, e, z]第 15 个是 z，栈顶是 e，不同，压栈，栈变 [c, e, z]，到头也没人能再和它配对。
19. 21栈 [c, e, z] = 答案字符串走完了。栈里从底到顶拼起来就是答案 = cez。一趟扫完，全程没回过头，两段连锁全靠栈自动接住。
20. 22刚才整条 cabccbaddxyyxez 走下来，指针只从左滑到右一遍，没有任何回头扫描——这就是栈把 O(n²) 压到 O(n) 的关键。
21. 25为什么是栈不是队列?因为消除只跟最近一个较劲——后进先出。凡是「当前元素只跟最近一个较劲」的题，第一反应就该想到栈。
22. 27stack 为空 → 读 top 崩!假如来第一个 a 时不先判空，直接拿 stack[-1] 去比，程序当场越界报错。所以条件里 stack 非空 必须写在前面。
23. 28栈空 → 直接压栈 [a]把判空写在前：栈空时短路、不去读栈顶，直接压栈 [a]，安全。这一行顺序就是这题的命门。
24. 29两两消光 → 栈空 []全相同的 aaaa：a 压、第二个 a 消，第三个 a 压、第四个 a 又消——两两抵消，栈最终清空。偶数全消、奇数会剩一个。

⚠️ 容易写错的地方

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

class Solution:
    def removeDuplicates(self, s):
        stack = []                 # 栈：存还没被消掉的字符
        for ch in s:
            if stack and stack[-1] == ch:  # 和栈顶相同
                stack.pop()        # 消掉一对
            else:
                stack.append(ch)   # 否则压栈
        return "".join(stack)

class Solution {
public:
    string removeDuplicates(string s) {
        string stk;                       // 用 string 当栈
        for (char ch : s) {
            if (!stk.empty() && stk.back() == ch)
                stk.pop_back();           // 消掉一对
            else stk.push_back(ch);       // 否则压栈
        }
        return stk;
    }
};

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder(); // 当栈用
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int len = sb.length();
            if (len > 0 && sb.charAt(len - 1) == ch)
                sb.deleteCharAt(len - 1);   // 消掉一对
            else sb.append(ch);             // 否则压栈
        }
        return sb.toString();
    }
}

复杂度

面试官可能追问