第3章｜栈与队列

Unit 01 · LeetCode #20 有效的括号

← Unit 00 基础
U01
Valid ParenthesesMatch · Top · Pending Openings

右括号出现时，
它只能关闭最近尚未关闭的左括号。

括号匹配并不是比较左右括号总数，而是维护嵌套顺序。栈顶始终代表当前最内层、最先需要被关闭的左括号。

LeetCode #20 题目模型三类括号、类型匹配与正确闭合顺序

题目要求

给定一个只包含 ()[]{} 六种括号字符的字符串 s，判断它是否有效。有效字符串要求：左括号必须由相同类型的右括号闭合；括号必须按正确顺序闭合；每个右括号都有对应的左括号。

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

输入、输出与约束

  • 输入：括号字符串 s
  • 输出：有效返回 True，否则返回 False
  • 1 ≤ len(s) ≤ 10⁴
  • s 仅由 ()[]{} 组成

示例

输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
输入：s = "([])"
输出：true
输入：s = "([)]"
输出：false

复杂度目标

一次从左到右扫描：时间复杂度 O(n)；最坏情况下全部为左括号，栈空间复杂度 O(n)。

Pending Opening

栈中只保存尚未被右括号匹配的左括号。已经完成配对的括号立即离开待处理状态。

Nearest Unclosed

栈顶是最近出现且尚未关闭的左括号。新的右括号必须首先与它匹配。

Type Matching

)→(、]→[、}→{。数量相等不能代替类型与顺序检查。

Final Empty Stack

扫描结束后栈必须为空；否则仍有左括号没有获得对应的右括号。

认知任务 1
根据当前字符和栈顶，决定本步应该压栈、弹栈还是失败
答案不能只看当前字符。右括号的动作取决于栈是否为空，以及栈顶左括号的类型。
括号扫描实验台状态尚未执行

输入字符串与扫描指针

读取当前字符前，先观察栈顶。

尚未匹配的左括号栈

) → (
] → [
} → {
读取字符
识别类型
检查栈顶
修改栈
确定状态
请先回答右侧问题，动画将展示本步状态变化。
扫描位置0
栈深度0
期待左括号—
当前结论待定
把栈契约编译为 Python填写关键表达式；主答案采用显式版本，便于与动画逐行对应。
if
if
执行匹配：
读取左括号：
扫描结束：return 
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        stack = []

        for char in s:
            if char in pairs:
                if not stack or stack[-1] != pairs[char]:
                    return False
                stack.pop()
            else:
                stack.append(char)

        return not stack

时间复杂度：O(n)
空间复杂度：O(n)
代码与括号栈逐行联动点击代码行可跳转到该行第一次执行的状态。
1class Solution:
2 def isValid(self, s: str) -> bool:
3 pairs = {")":"(", "]":"[", "}":"{"}
4 stack = []
6 for index, char in enumerate(s):
7 if char in pairs:
8 if not stack or stack[-1] != pairs[char]:
9 return False
10 stack.pop()
11 else:
12 stack.append(char)
14 return not stack

执行状态

当前输入s = "([])"
index / char—
stack
期待匹配—
判断 / 返回初始化
进入 Solution 类定义。
完成代码联动后进入 LeetCode #921 原题与迁移学习代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。

迁移题：LeetCode #921 使括号有效的最少添加

迁移不从代码开始。先确认新题允许什么操作、要求返回什么，再判断 #20 中哪些状态仍然必要，哪些状态可以被压缩。

1. 认识 #921 原题
2. 对照判断与修复
3. 映射四个状态变化
4. 拼装并运行官方样例
LeetCode #921｜使括号有效的最少添加 依据 LeetCode 官方题面整理 ↗

题目要求

给定一个只包含圆括号的字符串 s。一次操作可以在字符串任意位置插入一个 ( 或 )。返回把字符串变成有效括号串所需的最少插入次数。

class Solution: def minAddToMakeValid(self, s: str) -> int: # 返回最少插入次数

约束

  • 1 ≤ len(s) ≤ 1000
  • s[i] 只可能是 ( 或 )

官方示例

输入：s = "())"
输出：1
补入一个左括号即可修复多出的右括号。
输入：s = "((("
输出：3
三个未闭合左括号分别需要一个右括号。

有效括号串

空串有效；两个有效串拼接仍有效；在有效串外包上一对圆括号仍有效。本题允许修复，而不是发现错误后立即失败。

字符类型只有一种括号，不再需要区分 ()[]{} 三种类型。
允许操作只能插入括号，不能删除、替换或重新排列原字符。
优化目标返回最少插入次数，不是返回修复后的字符串。
扫描策略意外右括号需要补左括号；末尾剩余左括号需要补右括号。

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

读题检查 B｜为什么官方示例 s="())" 的答案是 1？

已经掌握：#20 有效的括号

输入：三种括号 ()[]{} 目标：判断是否有效，返回 bool 状态：stack 保存未匹配左括号的类型与顺序 意外右括号：立即 return False 扫描结束：stack 必须为空

准备迁移：#921 最少添加

输入：只有圆括号 () 目标：统计最少修复成本，返回 int 状态：balance 只保存未匹配左括号数量 意外右括号：additions += 1，然后继续扫描 扫描结束：剩余 balance 都要补右括号
保持不变仍然从左到右扫描；右括号只能消耗此前尚未匹配的左括号；已完成匹配的状态立即移除。
目标改变#20 遇到无法匹配的右括号就判错；#921 不能结束，而要把这次冲突转换成一次必需的插入成本。
为什么 stack 可以压缩成 balance？#20 必须记住栈顶究竟是 (、[ 还是 {；#921 的所有左括号完全同质。后续决策只需要知道“当前有没有可用左括号、共有多少个”，不再需要保存每个元素的类型和顺序。

先判断迁移幅度：下面哪句话最准确？

槽位 A｜需要哪两个整数状态？

槽位 B｜读取左括号时怎样更新？

槽位 C｜读取右括号时怎样处理“可匹配”和“意外出现”两种情况？

槽位 D｜扫描结束后为什么返回两部分之和？

两类缺口不会互相抵消：additions 记录扫描途中已经出现的“缺左括号”事件；最终 balance 记录仍未关闭的左括号，每一个都还缺一个右括号。
保留的核心语义状态始终表示“扫描前缀中仍未解决的括号需求”；匹配成功时立即消费一个未匹配左括号。
删除的类型信息不再需要 pairs 和字符栈，因为所有未匹配左括号都等价，只保留数量 balance。
新增的修复成本不能匹配的右括号不再导致失败，而是让 additions 增加1；最后再补齐剩余左括号。

#20：冲突即失败

pairs = {...}
stack = []
for char in s:
    if char in pairs:
        if not stack or stack[-1] != pairs[char]:
            return False
        stack.pop()
    else:
        stack.append(char)
return not stack

#921：冲突转化为修复成本

balance = 0
additions = 0
for char in s:
    if char == "(":
        balance += 1
    elif balance > 0:
        balance -= 1
    else:
        additions += 1
return additions + balance
官方样例运行轨迹：s = "())"0/0
未匹配左括号 balance0
已补左括号 additions0
当前最少添加数0
迁移不变量balance 表示前缀中尚未匹配的左括号；additions 表示前缀中已经无法由未来字符补救、必须插入的左括号数量。
可选挑战：脱离槽位，独立重写完整代码

编辑器保留了函数、状态初始化和循环骨架。请自行补回左括号、右括号和最终返回逻辑。

先完整运行官方样例，再尝试脱离槽位重写。

Unit 01 Skill：最近未闭合对象优先匹配

扫描括号字符串时，先识别未完成状态需要保存哪些信息。多种括号需要用栈保存类型与顺序；只有一种同质括号时，可以把栈压缩为数量。题目目标从“判断是否合法”变为“计算最少修复成本”后，原本的失败分支也要转化为可累计状态。

主问题#20：栈保存未匹配左括号
迁移问题#921：balance + additions
迁移类型容器状态压缩为计数状态
保持的不变量状态只描述扫描前缀中尚未解决的需求
目标变化布尔判定 → 最小修复成本
复杂度时间 O(n)，额外空间 O(1)