AlgoNote 算法通关手册：LeetCode 0020「有效的括号」——栈匹配问题的经典实战解析

• 教程
• 文档
• 知识库

本文导读：本篇以「算法通关手册」（AlgoNote）中 LeetCode 0020「有效的括号」题解为主体，系统讲解括号匹配问题的栈解法，并结合仓库中顺序栈、链式栈的源码实现说明栈结构在括号匹配中的底层原理。读完本文，你将掌握「后进先出（LIFO）」栈在字符串配对校验中的标准套路，并能够将其迁移到()、[]、{}三类括号混排的任意匹配场景。

1. 题目概览

题目：0020. 有效的括号 - 力扣

• 标签：栈、字符串
• 难度：简单

题目大意：给定一个只包括'('、')'、'{'、'}'、'['、']'的字符串s，要求判断字符串s是否有效（即括号是否匹配）。

有效字符串需满足的条件：

1. 左括号必须用相同类型的右括号闭合；
2. 左括号必须以正确的顺序闭合。

示例：

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

这道题是栈结构最典型的应用场景之一。在仓库的栈基础知识文档中，括号匹配问题被明确列为「栈的经典应用」之首，并关联了本仓库中的最小栈、基本计算器 II、逆波兰表达式求值、字符串解码 等练习题目，形成了一条完整的「栈应用」刷题链。

2. 前置知识：栈与括号匹配的关系

2.1 栈的核心特性

栈（Stack）：一种线性表数据结构，只允许在表的一端（栈顶）进行插入和删除操作，遵循**后进先出（LIFO）**原则——最后放入的元素最先被取出。

栈的三个基本操作：

• 入栈（Push）：在栈顶加入一个新元素；
• 出栈（Pop）：移除并返回栈顶元素；
• 查看栈顶（Peek）：只查看栈顶元素，不将其移除。

2.2 为什么栈天然契合括号匹配

括号匹配问题具有「最近匹配」的结构特征：一个右括号应当与最近一次出现的、尚未配对的同类型左括号配对，而栈顶恰好是「最近入栈、尚未弹出的元素」。因此，用栈保存未匹配的左括号，每次遇到右括号时检查栈顶是否为对应类型的左括号，就能精确模拟括号的嵌套与闭合顺序——这与现实中括号层层嵌套的书写结构完全一致。

2.3 仓库中的栈实现参考

仓库在 codes/python/03_stack_queue_hash_table/stack_sequential_stack.py 提供了顺序栈的实现（基于列表 + 栈顶指针top，top == -1表示空栈），在 stack_link_stack.py 提供了链式栈的实现（基于单链表头插法）。题目解法中直接使用 Python 内置list()充当栈，append()即入栈、pop()即出栈、stack[-1]即查看栈顶，其行为与仓库中的顺序栈实现完全对应，二者对比可帮助你理解「逻辑栈」与「物理实现」之间的关系。

3. 解题思路：栈

3.1 思路分析

1. 奇偶性预判：括号成对出现，若字符串长度为奇数，则必然无法完全匹配，直接返回False。这一剪枝可以在常数时间内排除一半左右的非法输入，避免无意义的遍历。
2. 遍历匹配：使用栈stack保存未匹配的左括号，依次遍历字符串s中的每一个字符：
   • 遇到左括号(、[、{时，将其入栈；
   • 遇到右括号)、]、}时，检查栈顶元素是否为与当前右括号同类型的左括号：
     • 若匹配，则弹出栈顶元素，继续向前遍历；
     • 若不匹配（或栈为空），说明括号不合法，直接返回False。
3. 收尾检查：遍历结束后再判断栈是否为空：
   • 栈为空，说明所有左括号均已正确配对，返回True；
   • 栈不为空，说明存在未配对的左括号（如"([)]"中的剩余元素），返回False。

这里有一个关键细节值得注意：遇到右括号时，若栈为空也要返回False。例如输入")("，遍历到第一个字符)时栈为空，无法与任何左括号匹配，直接判定非法——这一步避免了stack[-1]在空栈上引发索引错误。

3.2 参考代码

class Solution: def isValid(self, s: str) -> bool: # 奇数长度必然无法完全配对，直接返回 False if len(s) % 2 == 1: return False stack = list() # 用列表模拟栈，保存未匹配的左括号 for ch in s: # 左括号：入栈 if ch == '(' or ch == '[' or ch == '{': stack.append(ch) # 右括号：检查栈顶是否为同类型左括号 elif ch == ')': if len(stack) != 0 and stack[-1] == '(': stack.pop() else: return False elif ch == ']': if len(stack) != 0 and stack[-1] == '[': stack.pop() else: return False elif ch == '}': if len(stack) != 0 and stack[-1] == '{': stack.pop() else: return False # 遍历结束后栈为空才说明全部配对成功 return len(stack) == 0

上面的写法逻辑直白、便于理解。在此基础上，还可以用「字典映射」做一处更紧凑的等价改写：预先建立右括号到对应左括号的映射pairs = {')': '(', ']': '[', '}': '{'}，遍历时遇到右括号直接查询pairs[ch]与栈顶比较，从而把三段重复的elif合并为一段统一逻辑。两种写法的时间、空间复杂度相同，后者在括号类型增多时扩展性更好。

3.3 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为字符串s的长度。每个字符至多入栈一次、出栈一次，均为常数时间操作。
• 空间复杂度：$O(n)$，最坏情况下字符串全部由左括号组成（如"((((("），所有字符都会入栈。

需要说明的是：栈基础文档的示例代码给出的是 $O(1)$ 空间（该表述针对固定字符集的简化场景），而本题按最坏情况分析，栈中元素数量与输入规模相关，采用 $O(n)$ 是更严格且更通用的结论，本文以此为准。

4. 手工推演：算法执行过程

以输入s = "([{}])"为例，逐步推演：

遍历结束且栈为空，返回True。

再看两个非法输入：

• s = "([)]"：遍历到)时栈顶为[，类型不匹配，直接返回False。这说明类型一致与顺序正确两个条件缺一不可。
• s = "(()"：遍历结束后栈中残留一个(，最终返回False，说明「右括号都能匹配」还不够，还必须「所有左括号都被闭合」。

5. 进阶与延伸：从基础匹配到同类问题

掌握本题的栈解法后，可以沿着两条线继续深化：

其一，仓库内的同主题题解。「最长有效括号」是本题的困难级延伸——0032. 最长有效括号 要求找出最长有效括号子串的长度，其栈解法在本题基础上引入了「栈中存储下标 + 哨兵-1」的技巧，用于计算连续有效长度；栈基础文档 还收录了利用栈处理运算符优先级的基本计算器 II。此外，栈单调栈文档 展示了栈在「下一个更大元素」类问题中的应用，前缀目录索引 中维护了完整的「栈基础题目」列表，可作为刷题路线图。

其二，字符串处理中「配对校验」思路的推广。栈不仅能匹配括号，还能匹配 HTML/XML 标签闭合、JSON 结构校验、编译器词法分析中的符号配对等场景。核心模式是统一的：遇到「开启」符号入栈，遇到「闭合」符号与栈顶比对，类型匹配则弹出，遍历完检查栈空。理解了这一模式，你就能把本题的解法快速迁移到大量看似不同的题目上。

6. 总结

「有效的括号」虽然标记为简单题，却是理解栈这一数据结构的黄金入口：

• 一条主线：左括号入栈、右括号与栈顶比对、遍历后栈空即合法；
• 两个边界：奇数长度直接剪枝；遍历中遇空栈且遇右括号立即判非法；
• 一组延伸：栈存下标 + 哨兵可求解最长有效括号，同一数据结构支撑表达式求值、单调栈等进阶问题。

通过本仓库的题解文档、栈基础教程与顺序栈/链式栈源码三者对照学习，可以同时获得「题目解法—数据结构原理—底层实现」三个层次的完整认识，这正是 AlgoNote「算法通关手册」的设计初衷。

• 教程
• 文档
• 知识库