LeetCode 1047 题解：删除字符串中的所有相邻重复项——栈与数组模拟的多种实现（LogicStack-LeetCode 刷题笔记）

• 教程
• 文档

导读

本文围绕 LeetCode 第 1047 题「删除字符串中的所有相邻重复项」展开，这是「宫水三叶的刷题日记」刷穿 LeetCode 系列中 Tag 为「队列」「模拟」的入门级题目。题目的核心是：反复删除字符串中相邻且相同的两个字母，直到无法继续删除为止，并返回最终唯一的结果。读完本文，你将掌握这类"相邻消除"问题的通解思路——利用栈（或双端队列）的单趟扫描法，并能对比"自带数据结构"与"纯数组模拟"两类实现方式在代码简洁度、常数开销上的差异，同时理解hh/tt双指针模拟栈/队列的底层写法，可直接应用于同系列更多栈与模拟类题目。

题目回顾与题意分析

题目原始描述与约束如下（完整题解见 LeetCode/1041-1050/1047. 删除字符串中的所有相邻重复项（简单）.md）：

• 给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除它们；
• 在S上反复执行该操作，直到无法继续删除；
• 返回完成所有删除操作后的最终字符串，答案保证唯一。

示例：

输入："abbaca" 输出："ca" 解释： 在 "abbaca" 中，先删除 "bb"（两字母相邻且相同，这是当时唯一可执行的删除），得到 "aaca"； 此时又只有 "aa" 可以删除，最终得到 "ca"。

数据范围提示：

• 1 <= S.length <= 20000
• S仅由小写英文字母组成

为什么"答案保证唯一"？这一点值得注意：虽然不同的删除顺序在中间过程可能不同，但由于"相邻且相同"的消除具有确定性的最终形态，本题保证最终字符串唯一，因此无需处理多解问题，直接做单趟模拟即可。

核心思路：栈的单趟扫描

观察操作的本质：每次删除一对相邻相同字符后，原本不相邻的字符可能变成新的相邻对（例如"aaca"中删除"aa"后"c"与"a"拼接，但本例最终只剩"ca"）。这种"后出现的字符可能与前一个未匹配字符发生配对"的特性，天然契合栈的先进后出结构：

• 从左到右扫描每个字符；
• 若当前字符与栈顶相同，说明二者是相邻重复项，弹出栈顶（即完成一次删除）；
• 否则将当前字符压入栈顶；
• 扫描结束后，栈中剩余元素按顺序即为最终答案。

一次遍历即可完成全部消除，因为每次弹出栈顶后，新字符会继续与新的栈顶比较，自动覆盖了"删除后产生新相邻对"的情况。该思路的时间复杂度为O(n)，空间复杂度为O(n)（栈空间）。

解法一：自带栈（双端队列）实现

在 Java 中直接使用Deque<Character>（如ArrayDeque）作为栈，代码最直观：

class Solution { public String removeDuplicates(String s) { char[] cs = s.toCharArray(); Deque<Character> d = new ArrayDeque<>(); for (char c : cs) { if (!d.isEmpty() && d.peekLast().equals(c)) { d.pollLast(); } else { d.addLast(c); } } StringBuilder sb = new StringBuilder(); while (!d.isEmpty()) sb.append(d.pollLast()); sb.reverse(); return sb.toString(); } }

要点说明：

• 这里使用addLast/pollLast将双端队列当作栈使用（操作末端），逻辑与标准栈一致；
• 出栈时从尾部依次弹出，得到的是逆序结果，因此拼接后需reverse()还原顺序；
• 时间复杂度O(n)，空间复杂度O(n)。

解法二：纯数组模拟栈

自带容器虽然直观，但装箱（Character对象）、方法调用都会带来额外常数开销。由于本题字符总长最多 20000，我们可以直接用一个char[]数组配合两个指针模拟栈：

class Solution { public String removeDuplicates(String s) { char[] cs = s.toCharArray(); char[] d = new char[s.length()]; int hh = 0, tt = -1; for (char c : cs) { if (hh <= tt && d[tt] == c) { tt--; } else { d[++tt] = c; } } StringBuilder sb = new StringBuilder(); while (hh <= tt) sb.append(d[tt--]); sb.reverse(); return sb.toString(); } }

这段代码中的指针约定是该仓库题解系列中反复出现的经典写法：

• hh（队头指针）初始为0，tt（队尾指针）初始为-1，表示空容器；
• hh <= tt用于判断容器是否非空；
• 压栈：d[++tt] = c；出栈：tt--；
• 由于按"栈"语义操作（只从尾部进出），最终从尾部依次弹出并reverse()即可。

时间复杂度O(n)，空间复杂度O(n)。相比解法一，避免了对象装箱开销，在数据量大时性能更优。

解法三：自带双端队列，按队列语义输出

如果从另一端（pollFirst）弹出元素，同一份"入队/出队"逻辑就从"栈视角"变成了"双端队列视角"，此时元素天然保持原顺序，无需reverse()：

class Solution { public String removeDuplicates(String s) { char[] cs = s.toCharArray(); Deque<Character> d = new ArrayDeque<>(); for (char c : cs) { if (!d.isEmpty() && d.peekLast().equals(c)) { d.pollLast(); } else { d.addLast(c); } } StringBuilder sb = new StringBuilder(); while (!d.isEmpty()) sb.append(d.pollFirst()); return sb.toString(); } }

对比解法一：维护逻辑完全相同（尾部比较、尾部弹出），差异仅在于最终收集元素的方向——从头部弹出则顺序正确。这体现了Deque同时具备"栈"与"队列"双重语义的灵活性。

解法四：数组模拟双端队列

同样，在数组模拟版本中，从头部依次弹出即可直接得到正序结果：

class Solution { public String removeDuplicates(String s) { char[] cs = s.toCharArray(); char[] d = new char[s.length()]; int hh = 0, tt = -1; for (char c : cs) { if (hh <= tt && d[tt] == c) { tt--; } else { d[++tt] = c; } } StringBuilder sb = new StringBuilder(); while (hh <= tt) sb.append(d[hh++]); return sb.toString(); } }

注意此处弹出方向为d[hh++]，而解法二为d[tt--]。由于元素都是从尾部d[++tt]写入的，hh到tt区间内保存的正是最终答案的正序，从头部弹出无需反转。

解法五：纯数组 + 直接构造字符串

既然最终结果就是d[0..tt]这一段连续区间，甚至不需要StringBuilder循环拼接，直接用字符串构造器即可：

class Solution { public String removeDuplicates(String s) { char[] cs = s.toCharArray(); char[] d = new char[s.length()]; int hh = 0, tt = -1; for (char c : cs) { if (hh <= tt && d[tt] == c) { tt--; } else { d[++tt] = c; } } return new String(d, 0, tt + 1); } }

这是五种实现中最简洁的收尾写法：new String(d, 0, tt + 1)直接以数组d的[0, tt]区间构造最终字符串，省去了逐字符拼接与反转。同样为O(n)时间、O(n)空间。

五种实现的对比与选择

实际应试与工程中，解法二/解法五的数组模拟是兼顾性能与简洁度的优选；解法一/三则更强调代码可读性。五种写法的时间、空间复杂度一致（O(n)/O(n)），差异主要在于常数因子与代码风格。

仓库中的延伸与佐证

本题在该仓库中收录于多个 Tag 索引，可作为同类题目的检索入口：

• Index/栈.md 与 Index/队列.md：本题被同时归类到「栈」与「队列」两个 Tag 下（推荐指数 🤩🤩🤩🤩），说明"栈与双端队列等价"正是本题的题眼；
• Index/模拟.md：本题同样出现在「模拟」索引中，属于"用数据结构模拟删除过程"的典型代表。

同系列题目中可以对比学习：

• 26. 删除有序数组中的重复项（简单） 与 80. 删除有序数组中的重复项 II（中等）：同样是"删除重复元素"，但基于有序数组 + 双指针原地处理，与本题的"栈消除"思路形成互补——前者强调空间复用，后者强调相邻消除的动态配对；
• 1190. 反转每对括号间的子串（中等）：同为「栈 / 双端队列」Tag 下的进阶题，展示了同一个Deque结构在更复杂消除场景（括号匹配 + 反转）中的复用；
• 1041. 困于环中的机器人（中等）：同为「模拟」Tag，可进一步体会"按规则逐步模拟状态"的通用方法论。

小结

「删除字符串中的所有相邻重复项」是一道"一题多解"的经典入门题：从思路层面，它揭示了相邻消除问题与栈结构的天然对应关系；从实现层面，它给出了从"自带容器"到"数组模拟"、从"栈语义"到"队列语义"的完整演进路径，是理解Deque双重语义与hh/tt双指针写法的绝佳载体。掌握本文的五种实现，你不仅能轻松 AC 本题，也能为后续「反转每对括号间的子串」等栈类进阶题打下坚实基础。

• 教程
• 文档