第3章｜栈与队列

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

← Unit 01
U02
Reduced Prefix StackCompare · Cancel · Restore

不要反复改写字符串，
让栈保存“已经消干净的前缀”。

删除一对相邻重复字符后，原本不相邻的两侧字符可能变成新邻居。真正需要保留的不是全部历史，而是当前前缀完成所有消除后的结果及其最后一个字符。

LeetCode #1047 题目模型Remove All Adjacent Duplicates In String

题目要求

给定仅由小写英文字母组成的字符串 s。一次操作可以删除两个相邻且相同的字母。重复执行删除，直到无法继续，返回最终字符串。最终结果具有唯一性。

class Solution: def removeDuplicates(self, s: str) -> str: pass

数据约束与复杂度目标

  • 1 ≤ len(s) ≤ 10⁵；
  • s 仅包含小写英文字母；
  • 目标实现：时间 O(n)，辅助空间 O(n)。

示例

输入：s = "abbaca"
输出："ca"
过程：abbaca → aaca → ca
输入：s = "azxxzy"
输出："ay"

本页主模型

从左到右读取字符。若当前字符等于栈顶，则弹出栈顶完成一对消除；否则压栈。扫描结束后，栈从底到顶就是最终字符串。

Adjacent Duplicate

只有当前相邻且相等的两个字符可以删除。删除会改变两侧字符的邻接关系。

Reduced Prefix

已经扫描的前缀执行完全部相邻消除后的规范结果，是本题真正有用的状态。

Stack Top

栈顶是当前有效前缀的最后一个字符，也是唯一可能与新字符形成重复对的位置。

Cancellation

相等时执行 pop，相当于当前字符与栈顶字符同时抵消；当前字符不再入栈。

先连接上一单元：栈顶仍是唯一需要读取的历史，但容器语义发生了变化Unit 01 → Unit 02
#20：尚未闭合的结构

stack 保存尚未匹配的左括号。新右括号只与最近未闭合的 stack[-1] 发生匹配。

→
#1047：已经规约的有效前缀

stack 保存已读前缀完成全部消除后的结果。新字符只与当前有效末尾 stack[-1] 发生抵消。

复用的不是“看到字符就压栈”，而是边界状态：栈顶代表唯一可能影响当前决策的最近对象；已经闭合或已经抵消的历史立即离开容器。
认知任务 1
删除 “bb” 后，为什么还不能立刻停止？
一次删除会让原本分隔开的字符成为新邻居，因此答案依赖删除后的动态状态，而不是原字符串中最初可见的重复对。
相邻消除实验台人工删除模式

输入与当前扫描状态

观察当前字符与它左侧仍存活的最后一个字符。

已完成消除的前缀栈

容器语义在人工阶段，先观察删除如何制造新的相邻关系。
读取状态
比较相邻
删除 / 保留
形成新邻居
更新结果
请选择右侧答案，页面会演示对应状态变化。
已读字符0
字符比较0
删除对数0
当前结果—
把“已消除前缀”编译为 Python填写关键表达式；每一行都必须能解释当前动画。
初始化容器：
若可抵消：if
抵消动作：
否则保留：
最终返回：
class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []

        for char in s:
            if stack and stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)

        return "".join(stack)

时间复杂度：O(n)
空间复杂度：O(n)
代码与字符串栈逐行联动点击代码行可跳转到该行第一次执行的状态。
1class Solution:
2 def removeDuplicates(self, s: str) -> str:
3 stack = []
5 for index, char in enumerate(s):
6 if stack and stack[-1] == char:
7 stack.pop()
8 else:
9 stack.append(char)
11 return "".join(stack)

执行状态

输入s = "abbaca"
index / char—
stack
比较结果—
当前前缀 / 返回""
进入 Solution 类定义。
完成代码联动后进入 LeetCode #1209 迁移练习代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。

迁移题：LeetCode #1209 删除字符串中的所有相邻重复项 II

先完整理解新题，再迁移 #1047 的“规约前缀栈”。本题真正新增的不是另一个循环，而是让栈顶同时记住字符与当前连续次数。

1. 认识 #1209 原题
2. 对照两字符与 k 字符删除
3. 映射四个语义变化
4. 拼装并运行官方样例

LeetCode #1209｜题目要求

给定字符串 s 和整数 k。一次操作可以选择 k 个相邻且相同的字母并删除，使删除片段的左右两侧重新连接。重复执行，直到无法继续，返回最终字符串；题目保证最终答案唯一。

class Solution: def removeDuplicates(self, s: str, k: int) -> str: # 返回完成所有 k 倍重复项删除后的字符串

约束

  • 1 ≤ len(s) ≤ 10⁵
  • 2 ≤ k ≤ 10⁴
  • s 仅包含小写英文字母

官方示例

s = "abcd", k = 2
输出："abcd"
没有任何连续 2 个相同字符。
s = "deeedbbcccbdaa", k = 3
输出："aa"
eee、ccc → bbb → ddd，删除不断制造新邻居。
s = "pbbcggttciiippooaais", k = 2
输出："ps"
题面、示例与约束依据 LeetCode #1209 官方页面整理；此处采用中文教学转述。

读题检查 A｜函数最终返回什么？

读题检查 B｜为什么官方示例最终能从 deeedbbcccbdaa 变成 aa？

先确认操作单位：#1047 的一次消除固定为 2 个字符；#1209 的一次消除由输入参数 k 决定，而且删除后的新邻接仍可能触发后续操作。

已经掌握：#1047

栈元素：单个字符 char 相同判断：stack[-1] == char 命中动作：pop 一次，两个字符抵消 否则动作：append(char) 返回："".join(stack)

准备迁移：#1209

栈元素：[char, count] 字符组 相同判断：stack[-1][0] == char 命中动作：count += 1 达到 k：弹出整个字符组 返回：按 count 展开每个组
保持不变从左到右只扫描一次；stack 始终表示已读前缀完成全部合法删除后的稳定结果；新字符只与栈顶组发生关系。
需要升级单个字符无法表达“已经连续出现了几次”，因此栈元素从字符升级为 [字符, 次数]。

哪一句最准确地描述迁移幅度？

槽位 A｜栈中每个元素应该保存什么？

槽位 B｜当前字符与栈顶字符相同时怎样更新？

槽位 C｜当前字符与栈顶不同，以及计数达到 k 时分别怎样做？

槽位 D｜扫描结束如何恢复最终字符串？

为什么不能继续使用 "".join(stack)？此时 stack 的元素不再是字符串字符，而是形如 ['e', 2] 的字符组；必须先把每组还原成对应数量的字符。
复用的控制骨架一次线性扫描；只观察栈顶；完成删除的组立即离开栈；剩余栈表示稳定结果。
新增的最小状态每个栈元素增加一个 count，恰好回答“当前末尾连续了多少次”。
关键删除时机先递增或新建组，再统一检查 count == k；达到阈值立即弹组。

#1047：两个字符抵消

stack = []
for char in s:
    if stack and stack[-1] == char:
        stack.pop()
    else:
        stack.append(char)
return "".join(stack)

#1209：字符组达到 k 后删除

stack = []
for char in s:
    if stack and stack[-1][0] == char:
        stack[-1][1] += 1
    else:
        stack.append([char, 1])
    if stack[-1][1] == k:
        stack.pop()
return "".join(char*count ...)
官方样例轨迹：deeedbbcccbdaa / k=30/0
点击“运行官方样例”开始。
当前字符：—当前规约结果：""最终目标："aa"
可选挑战：脱离槽位，独立重写完整代码

主流程已经完成。这里保留控制骨架，你需要补回字符组更新、达到 k 后弹组和最终展开。

Unit 02 Skill：用栈维护已经完成规约的前缀

当新输入只可能与“当前稳定结果的最后一组”发生反应时，栈顶就是唯一必要历史。#1047 的栈顶只需保存字符；#1209 因删除阈值可变，必须进一步保存该字符组的连续次数。

题号 / 题型#1047 · 相邻消除
主表示stack = 已扫描前缀的稳定规约结果
核心不变量处理 char 前，stack 已完成此前所有合法删除
基础操作相等 pop；否则 append
迁移升级字符 → [字符, 连续次数]
复杂度时间 O(n)，空间 O(n)