【LeetCode刷题日记】1047：双栈法与双指针法巧妙消除相邻重复字符

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要本文针对LeetCode 1047题删除字符串中的所有相邻重复项提出了两种解法。第一种使用Deque栈结构通过压栈和弹栈操作消除相邻重复字符最后反转剩余字符得到结果。第二种采用双指针法将原数组模拟为栈通过快慢指针实现原地修改空间效率更高。两种方法的时间复杂度均为O(n)但双指针法将空间复杂度优化至O(1)。文章详细分析了两种实现的核心逻辑、性能差异和适用场景并提供了完整的Java代码实现。题目背景LeetCode1047给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。在 S 上反复执行重复项删除操作直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。示例输入abbaca输出ca解释例如在 abbaca 中我们可以删除 bb 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 aaca其中又只有 aa 可以执行重复项删除操作所以最后的字符串为 ca。提示1 S.length 20000S 仅由小写英文字母组成。题目解析第一种解法Deque栈实现本题要删除相邻相同元素相对于20. 有效的括号 来说其实也是匹配问题20. 有效的括号 是匹配左右括号本题是匹配相邻元素最后都是做消除的操作。本题也是用栈来解决的经典题目。那么栈里应该放的是什么元素呢我们在删除相邻重复项的时候其实就是要知道当前遍历的这个元素我们在前一位是不是遍历过一样数值的元素那么如何记录前面遍历过的元素呢所以就是用栈来存放那么栈的目的就是存放遍历过的元素当遍历当前的这个元素的时候去栈里看一下我们是不是遍历过相同数值的相邻元素。然后再去做对应的消除操作。 如动画所示然后从栈中弹出剩余元素此时是字符串ac因为从栈里弹出的元素是倒序的所以再对字符串进行反转一下就得到了最终的结果。text遍历字符串 abbaca 步骤1: 栈空 → 压入 a 栈: [a] 步骤2: b ≠ 栈顶a → 压入 b 栈: [a, b] 步骤3: b 栈顶b → 弹出 b 栈: [a] ← 发现重复消除 步骤4: a 栈顶a → 弹出 a 栈: [] ← 发现重复消除 步骤5: c ≠ 栈顶(空) → 压入 c 栈: [c] 步骤6: a ≠ 栈顶c → 压入 a 栈: [c, a] 输出: 栈中剩余 [c, a] → 反转得到 ca代码实操我们先要实现栈我们这里使用Deque来实现栈ArrayDeque会比LinkedList在除了删除元素这一点外会快一点为什么用 ArrayDeque 而不是 LinkedList特性ArrayDequeLinkedList底层结构循环数组双向链表内存占用更小更大每个节点有前后指针随机访问O(1)O(n)插入/删除O(1)均摊O(1)CPU 缓存友好✅ 是❌ 否结论对于栈操作只在一端插入删除ArrayDeque 性能更好。接下来的判断当栈是空的时候或者栈顶的元素跟我们遍历的元素不相等时入栈如果栈顶跟我们遍历的元素相等时出栈则消除了重复的元素。逻辑分支表条件动作含义deque.isEmpty()push(ch)第一个字符无物可消deque.peek() ! chpush(ch)不同字符暂存等待deque.peek() chpop()相同字符互相抵消之后把结果进行反转text栈底 → 栈顶 [c, a] (a 是栈顶) pop() 顺序先取 a再取 c 如果直接拼接str a c ac ❌ 错误 正确做法str pop() str - 第一次str a a - 第二次str c a ca ✅题目答案使用 Deque 作为堆栈class Solution { public String removeDuplicates(String S) { //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点 //参考https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist ArrayDequeCharacter deque new ArrayDeque(); char ch; for (int i 0; i S.length(); i) { ch S.charAt(i); if (deque.isEmpty() || deque.peek() ! ch) { deque.push(ch); } else { deque.pop(); } } String str ; //剩余的元素即为不重复的元素 while (!deque.isEmpty()) { str deque.pop() str; } return str; } }第二种解法双指针法代码逻辑定义快慢指针这里就不用说了快指针负责读慢指针负责写主要的逻辑就是模拟栈的思想而不是实现栈我们可能会想重复的都是两个相同的元素而覆盖操作不是只能覆盖一个元素吗。其实这是对覆盖进行了误解。这就是我们用双指针方法的精髓我们用的是栈的思想但没有 new 任何栈对象。我们把数组本身当成了栈来用组件角色说明fast指针读指针遍历原字符串读取每个字符slow指针写指针/栈顶指针指向栈的下一个空位ch[slow] ch[fast]入栈操作把读到的字符写入栈中ch数组栈的存储空间模拟栈的物理内存ch[slow] ch[fast]; // 这就是入栈操作这里的覆盖操作其实就是入栈操作通过fast指针来读写进slow指针的位置其实就是我们模拟的栈char[] ch s.toCharArray(); // ← 这个数组就是栈 int slow 0; // ← slow 就是栈顶指针java // 查看栈顶元素 if (slow 0 ch[slow] ch[slow - 1]) { // ↑ ↑ // 当前字符 栈顶元素slow-1 // 要入栈 最后一个有效元素 } // 为什么是 slow-1 // 因为有效元素在 [0, slow) 区间 // 区间是左闭右开最后一个有效索引就是 slow-1概念含义位置slow下一个可用位置 / 栈的大小指向空位slow - 1栈顶元素的位置指向最后一个有效元素然后就是我们前面提到的是怎么消除两个元素的如果元素不相等时就相当于是入栈没什么好说的然后就是遇到相同元素的时候如果慢指针的元素和慢指针前一个的元素相等也就是出现了重复元素这里我们进行slow--模拟的就是出栈的操作slow就是栈顶的指针的下一个元素我们把这个slow指针后移了从而栈顶的指针也就移动了slow-1。同时另一个元素也没有入栈因此两个重复元素都没有了。满足了我们的需求。其实这不是真正意义上的移除操作我们只是通过指针来规定边界只看指针范围的内部因此我们是忽视了外界的元素。栈是一种「思想」不一定是「对象」概念说明逻辑上的栈一种数据结构思想后进先出LIFO物理上的栈代码中 new 出来的 Stack、ArrayDeque 对象这道题的关键我们用的是栈的思想但没有 new 任何栈对象。我们把数组本身当成了栈来用题目答案class Solution { public String removeDuplicates(String s) { char[] ch s.toCharArray(); int fast 0; int slow 0; while(fast s.length()){ // 直接用fast指针覆盖slow指针的值 ch[slow] ch[fast]; // 遇到前后相同值的就跳过即slow指针后退一步下次循环就可以直接被覆盖掉了 if(slow 0 ch[slow] ch[slow - 1]){ slow--; }else{ slow; } fast; } return new String(ch,0,slow); } }核心差异对比表对比维度显式栈Deque双指针模拟栈空间复杂度O(n)O(1)是否需要额外容器需要new ArrayDeque()不需要原数组当栈用最终结果处理需要反转栈是倒序直接截取无需反转代码可读性高逻辑清晰中需要理解栈模拟是否修改原数据否是修改原字符数组内存分配堆上分配新对象无额外分配适用场景通用不介意额外空间追求极致性能/空间指标显式栈双指针时间复杂度O(n)O(n)空间复杂度O(n)O(1)内存分配次数2次栈StringBuilder0次只用了原数组CPU缓存友好一般好连续内存访问最后反转需要 O(n)不需要结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励