1047. 删除字符串中的所有相邻重复项（Remove All Adjacent Duplicates In String）¶

频次 ★★★ · 难度 🟢 · 高频：全厂

题目¶

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 s 上反复执行重复项删除操作，直到无法继续删除。返回最终的字符串。

示例：

输入: s = "abbaca"
输出: "ca"
解释: 删除 "bb" 得到 "aaca"，再删除 "aa" 得到 "ca"

思路¶

像消消乐一样，每次删除相邻重复项后可能产生新的相邻重复项，需要"回头看"——这正是栈的典型应用：

遍历字符串，栈顶元素与当前字符相同时弹出（消除），否则压入。最后栈中剩余字符即为结果。

用 StringBuilder 模拟栈（比 Deque<Character> 更省空间，且直接转字符串），StringBuilder 的最后一个字符即"栈顶"。

代码¶

// StringBuilder 模拟栈
public String removeDuplicates(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        int len = sb.length();
        if (len > 0 && sb.charAt(len - 1) == c) {
            sb.deleteCharAt(len - 1); // 弹出（消除）
        } else {
            sb.append(c); // 压入
        }
    }
    return sb.toString();
}

// Deque 栈（更直观）
public String removeDuplicates(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == c) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pollLast()); // 从栈底取，保持原顺序
    }
    return sb.toString();
}

复杂度¶

时间：O(n) — 每个字符入栈/出栈最多一次
空间：O(n) — 栈（或 StringBuilder）最多存储所有不重复的字符

边界条件¶

空字符串：返回空字符串
无相邻重复字符（如 "abc"）：所有字符压入栈，返回原字符串
全部可消除（如 "aabb"）：栈为空，返回空字符串

变式¶

双指针原地修改：用 slow 指针表示"栈顶"，fast 指针遍历，chars[slow] == chars[fast] 则 slow--，否则 chars[++slow] = chars[fast]。空间 O(1)（除输入数组外），类似 27. 移除元素的快慢指针套路。
递归删除：每次扫描并删除所有相邻重复项，递归直到没有变化，但时间复杂度最坏 O(n²)，不推荐。

易错点¶

StringBuilder 删除最后一个字符用 deleteCharAt(len - 1)，不是 deleteCharAt(len)——索引从 0 开始
Deque 版最后拼字符串时，栈顶存的是最后入栈的字符，需要从栈底取（pollLast() 或逆序）才能保持原顺序
注意 sb.length() 在 deleteCharAt 后减小，不要用旧的 len 变量
优先用 StringBuilder 当栈：它的最后一个字符就是栈顶（append = push，deleteCharAt(len-1) = pop），结束时天然就是正序结果。用 Deque 反而要导出到 StringBuilder 再 reverse() 一次，多绕一圈；且用 Deque 时若以 chars[0] 起步就得为空串特判，用 foreach 从头遍历可省掉特判
len > 0 && sb.charAt(len-1) == c 里的 len > 0 不只是防越界，也是「第一个字符无条件入栈」的表达：空栈没有栈顶可比，短路后直接走 append
栈顶的准确语义是「最近一个还没被消除的字符」，不一定是原串的前一个字符（中间可能已被消掉）。如 "abba" 处理最后的 a 时，栈顶是原串第 1 个 a，不是第 3 个 b
删末尾可用 sb.setLength(len - 1) 代替 sb.deleteCharAt(len - 1)——setLength 只改长度计数，无数组移动，更快（deleteCharAt 一般 O(n)，此处删的是末尾才恰好 O(1)）

面试追问¶

为什么这题必须用栈？ 因为删除后可能产生新的相邻重复项，需要"回头看"上一个没有被删除的字符——这正是栈 LIFO 特性（每次只关心最近一个未删除的字符）。用双指针遍历做不到，因为删除后字符位置前移，需要不断回退检查。
如果要求原地修改（输入是 char[]）？ 用快慢指针：slow 初始为 -1，fast 从 0 遍历，匹配时 slow--，否则 chars[++slow] = chars[fast]。这本质上是把 char[] 的 [0..slow] 当作栈来用。

关联题¶

同套路：20. 有效的括号 —— 栈处理"配对消除"的经典模板
进阶：1209. 删除字符串中的所有相邻重复项 II —— 每次删除 k 个重复项，栈需要记录字符和连续出现次数
知识点：栈的"回看上一个"特性在括号匹配、表达式求值、路径简化等场景中反复出现