教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文导读本篇以「算法通关手册」AlgoNote中 LeetCode 0020「有效的括号」题解为主体系统讲解括号匹配问题的栈解法并结合仓库中顺序栈、链式栈的源码实现说明栈结构在括号匹配中的底层原理。读完本文你将掌握「后进先出LIFO」栈在字符串配对校验中的标准套路并能够将其迁移到()、[]、{}三类括号混排的任意匹配场景。1. 题目概览题目0020. 有效的括号 - 力扣标签栈、字符串难度简单题目大意给定一个只包括(、)、{、}、[、]的字符串s要求判断字符串s是否有效即括号是否匹配。有效字符串需满足的条件左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合。示例输入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 提供了顺序栈的实现基于列表 栈顶指针toptop -1表示空栈在 stack_link_stack.py 提供了链式栈的实现基于单链表头插法。题目解法中直接使用 Python 内置list()充当栈append()即入栈、pop()即出栈、stack[-1]即查看栈顶其行为与仓库中的顺序栈实现完全对应二者对比可帮助你理解「逻辑栈」与「物理实现」之间的关系。3. 解题思路栈3.1 思路分析奇偶性预判括号成对出现若字符串长度为奇数则必然无法完全匹配直接返回False。这一剪枝可以在常数时间内排除一半左右的非法输入避免无意义的遍历。遍历匹配使用栈stack保存未匹配的左括号依次遍历字符串s中的每一个字符遇到左括号(、[、{时将其入栈遇到右括号)、]、}时检查栈顶元素是否为与当前右括号同类型的左括号若匹配则弹出栈顶元素继续向前遍历若不匹配或栈为空说明括号不合法直接返回False。收尾检查遍历结束后再判断栈是否为空栈为空说明所有左括号均已正确配对返回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「算法通关手册」的设计初衷。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 0020 Valid Parentheses基于栈的括号匹配校验算法全解析多语言实现LeetCode 0020 Valid Parentheses基于栈的括号匹配校验算法全解析多语言实现 导读 Valid Parentheses 有效的示例工程教程单调栈Monotone Stack通关指南原理、通用模板与 LeetCode 经典例题实战AlgoNote 算法通关手册单调栈Monotone Stack通关指南原理、通用模板与 LeetCode 经典例题实战AlgoNote 算法通关手册 单调栈是《AlgoNote教程文档知识库KVAE-Audio 音频潜在空间编码实战48kHz 全频带重建64 维潜在向量一步到位KVAE Audio 音频潜在空间编码实战48kHz 全频带重建64 维潜在向量一步到位 如果你正在做音频生成比如文本转音频、AI 配乐多半被同一个问教程文档知识库上一篇GPUStack企业级部署实战从架构设计到性能调优的完整指南下一篇Attend-and-Excite革命性AI图像生成优化方案解决Stable Diffusion多对象生成难题创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考