LeetCode 20. 有效括号：栈的第一课与匹配的通用模型

题目与栈的选择

LeetCode 20：给定只含 ()[]{} 的字符串，判断括号是否有效——有效 = 每个左括号都有同类型的右括号正确闭合，且闭合顺序正确。

输入："{[]}"  输出：true
输入："{(})"  输出：false（交叉闭合无效）
输入："(]"    输出：false（类型不匹配）

为什么用栈：括号的有效性有个关键性质——「最近打开的括号必须最先关闭」（后进先出）——{[]} 里最内层的 [] 先闭合、外层 {} 后闭合——「后进先出」正是栈的定义——「识别『后进先出』的结构特征」是选择栈的判断依据——遇到「最近的未处理项优先处理」的问题，栈是第一候选。

解法：左进右配

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':              # 左括号：进栈
            stack.append(ch)
        else:                        # 右括号：配对出栈
            if not stack or stack.pop() != pairs[ch]:
                return False         # 空栈（无左可配）或类型不匹配
    return not stack                 # 栈空 = 全部配对

「右括号驱动」的设计：不是「遇到左括号就去栈里找配对」，而是「右括号来时才知道要配谁」——「被动等待」的遍历模式：左括号只管入栈、右括号发起配对——「配对的方向性」：括号配对永远由右括号触发——这个模式在表达式求值等题中同样成立。三个失败条件的枚举：失败一：右括号时栈空（(] 开头是右——没有左可配——「无中生有」）；失败二：出栈类型不匹配（(]——类型错——「张冠李戴」）；失败三：遍历结束栈非空（((——左括号悬空——「有始无终」）——「三个失败条件」就是这道题的完整边界——漏一个就是 WA——「奇数长度」的快捷剪枝（len(s) % 2 == 1 直接 false——奇数个括号必有一边落单——「奇偶剪枝」的通用性**。

graph TD
    A[遍历字符串] --> B{左括号?}
    B -->|是| C[入栈]
    B -->|否| D{栈空?}
    D -->|是| E[false: 无左可配]
    D -->|否| F{出栈与类型匹配?}
    F -->|否| E
    F -->|是| G[继续]
    G --> H{遍历结束}
    H --> I[栈空? true : false]

「匹配模型」的泛化：栈思想的延伸

模型一：表达式求值。LeetCode 224/227 基本计算器——「括号嵌套」用栈（遇到 ( 压栈保存状态、遇到 ) 弹栈恢复——「保存现场/恢复现场」——与函数调用栈同构——「递归的显式化」：递归本质就是系统栈——「括号匹配 = 递归结构」——表达式求值的栈是「递归的显式化」的典型。模型二：编辑器的撤销。撤销操作（Ctrl+Z）——「最近的操作先撤销」——操作栈——「撤销栈」是每个编辑器的标配——重做（Redo）则需要另一个栈（撤销时把操作压进重做栈——「双栈」的协同。模型三：浏览器的后退前进。后退栈 + 前进栈——「后退清空前进栈」的细节——「栈在产品中的日常存在」——用户无感但无处不在。模型四：函数调用栈。递归的底层（「递归深度 = 栈深度」——链表递归反转篇的 O(n) 栈——栈溢出（stack overflow——「递归深度」的工程限制——「把递归改栈」的手法（显式栈模拟递归——「二叉树遍历的迭代化」**是这一手法的经典应用（栈保存待访问节点。

「有效括号」的进阶变体：最长有效括号（LeetCode 32）——库内已有专文（栈、DP、一次遍历三思路）——从「判断有效」到「最长有效」——「同一主题的难度阶梯」：20 判断 → 32 最长 → 22 生成（回溯）——「括号家族」的完整谱系——「一题三阶」的学习路径。

栈的进阶：单调栈与「表达式求值」

栈思想的进阶：单调栈的原理回顾与表达式求值的栈应用。「单调栈的复习」：「单调栈的原理」（栈内元素保持单调——「新元素破坏单调性时」弹出——「弹出的意义」：被弹出的元素找到了它的答案（下一个更大元素——「739 每日温度」（库内已有——「单调栈的 O(n)」（每个元素最多进栈出栈一次——「摊还 O(1)」——「单调栈的适用」（「找下一个更大/更小」——「next greater」家族——「单调递增栈 vs 单调递减栈」（找更大用递减栈、找更小用递增栈——「方向的选择」——「栈的方向」=答案的方向——「84 柱状图」（库内已有——「单调栈的进阶」（「面积的计算」——「左右边界」的确定——「单调栈」的家族（每日温度、柱状图、下一个更大元素 II——「循环数组」的处理（「遍历两次」——「模 n」的技巧——「循环数组的单调栈」。「表达式求值」：「双栈法」：数字栈+运算符栈——「运算符的优先级」——「入栈的条件」（栈顶优先级 ≥ 当前——弹出计算——「括号的处理」（遇到左括号压栈——右括号弹到左括号——「224 基本计算器」（括号+加减——「227 基本计算器 II」（加减乘除——「乘除优先」的处理（「遇到乘除立即算」——「优先级的两层」——「表达式求值」的完整流程——「栈的应用」从括号匹配到表达式求值——「栈的思想」的深化——「LIFO 的每一个应用」都是「最近上下文优先」——括号匹配、撤销、表达式、递归调用栈——「栈是「上下文管理」的数据结构。栈的进阶总结：单调栈（方向选择、循环数组）+表达式求值（双栈法、优先级）——「栈」的适用性判断：「问题中存在『最近的未处理项优先』的结构时」用栈——「单调栈」是「栈+有序性」的组合——「表达式求值」是「栈+优先级」的组合——「栈的思想」在组合中展现威力——「掌握栈的进阶，就是掌握「栈+什么」的组合思维。

有效括号的高频问答：退化分析、最长变体与真实编译器

问题一：如果字符串只有一种括号，还需要栈吗？——不需要，一个计数器就够：遇左加一、遇右减一，中途出现负数或结尾不为零即无效。本质是栈退化成了计数器——单类型括号时栈顶永远是同一种括号，我们只关心数量、不关心身份；多类型时身份才重要，计数器分辨不了 (] 的张冠李戴。这个问题的价值在「数据结构随问题退化」的意识：约束变弱时，O(n) 的栈应主动降级成 O(1) 的计数器；反过来约束变强（比如还要求输出每个括号对的配对位置）时，栈里存的也要从字符升级成下标。面试中先做这层退化/强化分析再动手，是「按需设计」的信号，比上来就写通用栈高一个层次。

问题二：最长有效括号（LeetCode 32）为什么不能在本题代码上小改得到？——本题求全局谓词（有效与否，一个布尔），32 求最优化量（最长有效子串的长度）——判定过程中被丢弃的现场信息（弹出的是什么、在哪个位置弹出的）恰恰是优化问题要用的。32 的栈解法精髓是栈里存下标而不是字符：栈底垫一个「最后一个无效位置」作为长度计算的基准，每次弹出后用「当前下标 − 新栈顶下标」更新最长值——存的东西一换，答案的维度就出来了。另一条路是 DP：dp[i] 表示以 i 结尾的最长有效长度，按「配对成功后能否继续向前拼接」分类转移。两条路殊途同归，共同的教训是：从判定到优化，先想清楚哪些「用完即弃」的现场信息需要保留——这是很多「会做判断题却做不出优化题」的根源。

问题三：真实编译器里的括号检查和这道题一样吗？——骨架一样（栈 + 配对表），工程版多三层：错误定位——报「第 3 行第 14 列的 ( 未闭合」，栈里存的除了符号还有行列号；错误恢复——编译器不会在第一个错误就停机，而是跳过可疑片段继续检查、一次报出所有错误（IDE 的红色波浪线要的就是这个体验）；更大的匹配家族——HTML 标签配对、模板引擎的 if/endif、代码编辑器的折叠层级判定，全是同构问题，只是「括号对」从固定三对变成符号表驱动。再往深一层就到了解析器：递归下降分析里，括号匹配融进文法规则、不再是独立算法。从这道题到编译器的距离，就是「算法骨架」到「工程实体」的距离——骨架三行代码，实体千万行工程，但栈的核心地位从未变过。

问题四：判断之外还有生成（LeetCode 22），括号家族的全貌是什么？——22 要求生成所有 n 对括号的合法组合，用回溯 + 剪枝：左括号没用完就可以加、右括号数小于左括号数就可以加——两条规则保证每个分支都通向合法解、不产生废枝。组合总数是卡特兰数 C(2n, n)/(n+1)（n=3 时 5 种），增长速度约 4ⁿ/n^1.5——「判断是 O(n)、最长是 O(n)、生成是指数」：括号家族用三道题把「判定、优化、枚举」三类问题的复杂度档次完整演示了一遍——家族刷完，三类问题的手感就都有了。

再补一个工程向的追问：编辑器里的「彩虹括号」是怎么实现的？——VS Code 的彩虹括号与点击高亮配对，用的是同一套栈模型的变体：扫描时给每个左括号记「嵌套深度」，深度取模映射到颜色表——颜色的交替就是嵌套层级的可视化；点击某个括号跳转到配对位置，跳的正是「栈里配对成功的另一个下标」。性能上的关键工程化是局部重扫：编辑器不会每次击键都全文件扫描，而是从当前行向上回溯到嵌套深度归零处、只重算局部状态——「全局算法 + 局部增量」是编辑器类功能的通用模式，有效括号的 O(n) 单趟扫描就是那个全局算法的地基——你每天写代码时看到的括号颜色，就是这道题在生产环境里的样子。

小结

有效括号的完整解析：栈的选择依据（「最近打开的最先关闭」= 后进先出——「识别 LIFO 特征」是选栈的判断依据）；解法（左进右配——右括号驱动的配对——三个失败条件：空栈、类型不匹配、遍历完栈非空——奇偶剪枝）；思想的泛化（表达式求值的现场保存、编辑器的撤销栈、浏览器的双栈、递归的显式化——「最近的未处理项先处理」是栈的通用模型）；括号家族（20 判断 → 32 最长 → 22 生成——难度阶梯）。给初学者的核心提醒：栈是最简单的数据结构（只有一个出入口），也是最容易「没想到用」的结构——判断标志就一个：「最近出现的元素需要最先处理吗」——是的用栈——这个判断在表达式求值、撤销功能、DFS 迭代化中反复出现——掌握「识别」，比掌握「实现」更重要。

栈是程序员的「后悔药」机制——最近的错误最先撤销——从括号匹配到 Ctrl+Z，它守护的都是同一件事：让最新的上下文随时可回退。