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

能做对，但每删一次就要重头再扫。像 aaaa… 这种，每趟只消掉一点，最坏要扫很多趟 → O(n²)。重复扫描就是慢的根源。

栈就是为「最近一个还没了结的」而生：和栈顶相同就 弹栈(消一对)，否则压栈。从左到右扫一遍，连锁反应被栈自动接住，你不用回头。

准备 · 换个更长的串：换条更长的串 cabccbaddxyyxez 把过程演透——它里头藏了两段连锁消除。上面是输入流，下面是空栈。指针从左到右逐字符扫，盯住栈怎么涨怎么消。

看 c · 栈空：第 1 个字符 c，栈是空的，没人能和它配对，压栈，栈变 [c]。

看 a · 栈顶 c≠a：第 2 个是 a，栈顶是 c，不一样，消不掉，压栈，栈变 [c, a]。

看 b · 栈顶 a≠b：第 3 个是 b，栈顶是 a，不同，继续压栈，栈一路涨到 [c, a, b]。

看 c · 栈顶 b≠c：第 4 个又是 c，栈顶是 b，不同，压栈，栈涨到 [c, a, b, c]——注意这串 cabc 一个都没消，全堆着。

看 c · 栈顶 c=c · 连锁起点：第 5 个是 c，栈顶正好也是 c——凑成一对！弹栈消掉，栈回到 [c, a, b]。消完后新露出的栈顶是 b，连锁就要开始了。

看 b · 栈顶 b=b · 连锁：第 6 个是 b，和刚露出的栈顶 b 又凑一对！弹栈消掉，栈剩 [c, a]，新栈顶变成 a。

看 a · 栈顶 a=a · 连锁到底：第 7 个是 a，又和栈顶 a 配对，再弹栈——一口气消了三对 cc、bb、aa！栈塌回 [c]。这就是栈替你自动接住的连锁反应。

看 d · 栈顶 c≠d：第 8 个是 d，栈顶是 c，不同，压栈，栈变 [c, d]。

看 d · 栈顶 d=d：第 9 个又是 d，和栈顶 d 配对，弹栈消掉，栈回到 [c]。

看 x · 栈顶 c≠x：第 10 个是 x，栈顶是 c，不同，压栈，栈变 [c, x]——第二段连锁正在埋伏笔。

看 y · 栈顶 x≠y：第 11 个是 y，栈顶是 x，不同，压栈，栈涨到 [c, x, y]。

看 y · 栈顶 y=y · 第二段连锁：第 12 个又是 y，和栈顶 y 配对，弹栈消掉，栈剩 [c, x]——新栈顶 x 露出来了。

看 x · 栈顶 x=x · 又连锁：第 13 个是 x，消掉 yy 后新露出的栈顶正好是 x——再凑一对！弹栈，栈又塌回 [c]。第二段连锁也被栈接住了。

看 e · 栈顶 c≠e：第 14 个是 e，栈顶是 c，不同，压栈，栈变 [c, e]。

看 z · 栈顶 e≠z：第 15 个是 z，栈顶是 e，不同，压栈，栈变 [c, e, z]，到头也没人能再和它配对。

扫描结束：字符串走完了。栈里从底到顶拼起来就是答案 = cez。一趟扫完，全程没回过头，两段连锁全靠栈自动接住。

刚才整条 cabccbaddxyyxez 走下来，指针只从左滑到右一遍，没有任何回头扫描——这就是栈把 O(n²) 压到 O(n) 的关键。

为什么是栈不是队列?因为消除只跟最近一个较劲——后进先出。凡是「当前元素只跟最近一个较劲」的题，第一反应就该想到栈。

雷区实演 · 栈空读栈顶：假如来第一个 a 时不先判空，直接拿 stack[-1] 去比，程序当场越界报错。所以条件里 stack 非空 必须写在前面。

雷区实演 · 加上判空就对了：把判空写在前：栈空时短路、不去读栈顶，直接压栈 [a]，安全。这一行顺序就是这题的命门。

边界实演 · 全相同 aaaa：全相同的 aaaa：a 压、第二个 a 消，第三个 a 压、第四个 a 又消——两两抵消，栈最终清空。偶数全消、奇数会剩一个。

边界三连：先想最小规模(空串)、最极端(全相同)、最普通(没得消)三种，代码就稳了。

面试追问：把「为什么一趟够」讲清楚，是这题面试的得分点。