栈解“有效的括号”：从LeetCode刷题到面试手写

做LeetCode刷题的人应该都遇到过“有效的括号”这道题它排在栈专题的前几名看起来简单到像是送分题但你真拿笔在纸上一步步推演、或者面试时突然被要求手写很容易暴露出很多隐藏问题。它要求我们判断一个只包含(、)、{、}、[、]的字符串是否满足两个条件左括号必须用相同类型的右括号闭合并且闭合顺序要正确。()[]{}是有效的([)]看起来左右数量对得上却是无效的。我先说结论这道题的标准解法是用栈遍历字符串左括号入栈遇到右括号就弹出栈顶元素比对类型最后栈空才有效。但真正把这道题吃透至少还要搞清楚四个问题为什么是栈、边界条件有哪些、复杂度能不能优化、同类题怎么延伸。这篇文章我会按照自己实际刷题的思路完整拆一遍代码用 Python但逻辑不绑定语言。1. 先拆题有效括号到底在验证什么1.1 题目约束与有效规则的本质题目给出的字符串长度有限通常认为最大长度在 10^4 级别所以一个 O(n) 的解法是肯定可以的。有效规则其实可以拆成两条每个右括号都要找到一个“最近的、还没被匹配的”同类型左括号。所有左括号都要在字符串结束前被匹配完。这两条规则本质上是“后进先出”的顺序。举个例子{[]}这个字符串从左往右看遇到{后遇到[然后遇到]此时能匹配的是最近的左括号[而不是远处的{接着遇到}再匹配{。这个顺序就像叠盘子先放上去的盘子最后才能取走。如果改成{[}]遇到第一个}时栈顶却是[类型对不上整个字符串就无效。1.2 为什么栈是天然适配的数据结构很多初学者会问能不能用计数器如果只有一种括号确实可以遇到左括号加一遇到右括号减一最后看是不是零。但题目给了三种括号单靠计数无法区分([)]这种交错情况的错误因为它的左括号数量和右括号数量相等计数结果为零但顺序是错的。栈恰好保存了左括号出现的顺序每次只关心最近一次出现的左括号。这种“最近匹配”逻辑和栈的 LIFO后进先出完全一致。编译器在解析表达式、IDE 在做括号高亮时底层也是同样的思路。你可以把栈想象成一个只能从顶部进出的篮子左括号放进去遇到右括号时就从篮子里取出最上面的那个左括号比对。取出的如果类型不匹配或者篮子已经空了说明这个右括号多余或顺序错误。1.3 常见的错误理解只数数量不辨顺序我见过有人拿到题第一反应是统计六种字符的数量然后判断左括号总数是否等于右括号总数再分别判断每种括号的数量是否相等。这个思路作为第一层过滤没问题但它绝对不是充分条件。[(])每种括号数量都相等却无效。还有人对“闭合顺序”理解成“只要两种括号不相交叉就行”但(([]))是嵌套([)]是交叉交叉一定无效嵌套可以。栈解法不用刻意区分嵌套和交叉它每次都检查栈顶交叉场景必然会在某个右括号处发现栈顶类型不匹配。2. 栈解法的完整代码与逐行拆解2.1 最直接的实现方式先写一版入门级代码只依赖列表的append和popdef isValid(s: str) - bool: stack [] for ch in s: if ch in ({[: stack.append(ch) else: if not stack: return False left stack.pop() if (left ( and ch ! )) or \ (left { and ch ! }) or \ (left [ and ch ! ]): return False return len(stack) 0这段代码逻辑很直白遇到左括号压栈遇到右括号先检查栈是否为空为空说明右括号多余不为空就弹出栈顶左括号用if判断三个配对条件。遍历结束后如果栈里还有残留左括号说明这些左括号没有对应的右括号同样无效。2.2 用哈希表替代一堆 if 判断三个if不算多但如果括号类型增加到四五种代码会变得很啰嗦。更工程化的写法是用字典维护配对关系def isValid(s: str) - bool: pair {): (, }: {, ]: [} stack [] for ch in s: if ch in pair: if not stack or stack[-1] ! pair[ch]: return False stack.pop() else: stack.append(ch) return not stack这里pair的 key 是右括号value 是对应的左括号。遍历时如果当前字符是右括号就检查栈顶是否为对应的左括号。注意stack[-1]在栈空时会抛异常所以先用not stack判断。把ch in pair作为判断条件左括号自然全部走else分支入栈代码可读性比连续if好很多。2.3 手动走一遍执行流程拿s ([{}])演示读入(是左括号入栈。栈[(]读入[入栈。栈[(, []读入{入栈。栈[(, [, {]读入}是右括号栈顶是{匹配弹出。栈[(, []读入]栈顶是[匹配弹出。栈[(]读入)栈顶是(匹配弹出。栈[]遍历结束栈空返回 True。再来一个错误示例s (]读入(入栈。读入]是右括号栈顶是(但pair[]]是[不等于(返回 False。2.4 刷题之外的工程化思考如果你在公司里写代码遇到这种括号匹配需求可能还会考虑字符串里混有普通字符怎么办、嵌套层级过深导致递归爆栈怎么办、用栈能不能做到流式判断。流式判断就是边读边处理不需要一次性载入整个字符串这在解析大文件时很有用。栈解法天然支持流式处理这也是它比“先统计所有字符再处理”更实用的原因之一。3. 边界条件与易错点排查刷题翻车实录3.1 空字符串算不算有效按 LeetCode 的定义空字符串被认为是有效的括号字符串。很多人在一开始会漏掉这个直接把return len(stack) 0写上其实已经处理了空串因为空串时栈本来就是空的返回 True。如果你在一开始写了if len(s) 0: return False那就错了。我见过不少同学因为题目没明说就被这题摆了一道。3.2 第一个字符就是右括号)(这种字符串第一轮遍历遇到)时栈是空的直接返回 False。这个逻辑在代码里已经体现if not stack or stack[-1] ! pair[ch]。很多人容易踩的坑是先写stack[-1]再检查栈空导致IndexError。正确的顺序永远是“先判空再取栈顶”。3.3 左右数量相同但括号交错([)]的完整判断过程是这样的读入(入栈。读入[入栈。读入)栈顶是[pair[)]是(两者不匹配返回 False。即使后面还有(和]算法已经提前终止。这说明栈解法不仅能判断“完整性”也能判断“顺序性”。提前终止是性能优势也符合短路判断的直觉。3.4 遍历结束后栈里还有残留(()这种字符串读到最后一个)时栈顶是(匹配弹出此时栈里还剩一个(遍历结束栈不为空返回 False。这个场景最容易被遗漏因为不少人只关注遍历过程中的匹配关系忘记最终收尾检查。3.5 题面没提但实际可能出现的字符LeetCode 这题已经限定只有六种括号但如果你把代码拿到生产环境去改很可能遇到空格、字母、中文括号甚至换行符。建议先过滤无用字符或者明确约定输入格式。我曾经在某个解析器里复用这道题的逻辑结果用户输入了全角括号直接被当作普通字符忽略导致校验失灵。所以真实项目里要先做白名单校验。4. 复杂度分析为什么标准解法就是最优解4.1 时间和空间复杂度标准栈解法的时间复杂度是 O(n)因为每个字符恰好入栈一次、出栈一次左括号入栈右括号触发弹栈主要动作都是 O(1) 的列表尾部操作。空间复杂度最坏是 O(n)当字符串全是左括号时所有字符都要进栈。4.2 能不能把空间压到 O(1)一个常见的贪心问题是只用三个计数器分别记录三种括号的出现次数能不能判断答案是不能因为计数器丢失了顺序信息。我用一个反例([)]三种括号各自数量相等计数器全部归零但它无效。所以对于三种括号并存的一般情况O(n) 空间是必要的这不是解法不够好而是问题本身需要记录历史顺序。那如果只考虑一种括号呢确实可以用一个整数变量代替栈遇到左括号加一遇到右括号减一中途小于零直接失败最后等于零成功。这在面试里可以作为“问题简化”的讨论点当括号类型从三种变成一种数据结构可以从栈退化成计数器。但题目明确是三种所以标准答案还是栈。4.3 如果试图用字符串替换做这件事有些新手会想到循环把()、[]、{}替换成空字符串最后看结果是否为空。这个思路在概念上没问题但最坏时间复杂度很高比如(((((((((())))))))))这种深度嵌套每轮替换只能消掉最中间的一对总共要执行 O(n) 轮替换每次替换又是 O(n) 的字符串复制整体 O(n^2)。LeetCode 上字符串长度如果达到 10^4这个做法会超时或非常慢。栈解法则是标准的 O(n)没有这个问题。4.4 什么时候需要额外思考内存优化如果括号字符串是几百万字符的长文本栈的最大深度可能接近字符串长度内存占用不容忽视。但可以换个角度很多情况下括号嵌套深度是有限的栈的深度不会超过最大嵌套深度而不是字符串长度。你可以在入栈前检查栈深度是否超过某个业务阈值超过就认为非法这样既能防止内存暴涨也能提前拦截明显恶意的输入。5. 从这道题延伸开的同类问题5.1 括号生成从验证到构造LeetCode 第 22 题要求生成所有有效的括号组合输入是n对括号输出所有合法序列。这道题从“验证”变成了“构造”但核心判断逻辑几乎一样。通常用回溯法在递归过程中维护左括号剩余数量和右括号剩余数量只有当前右括号剩余数大于左括号剩余数时才允许放右括号这样生成的序列一定有效。你做完“有效的括号”后应该立刻去试这题感受从“检查器”到“生成器”的思路迁移。5.2 最长有效括号从合法性到连续性第 32 题是高频难题求一个只包含左右括号的字符串中最长有效括号子串的长度。比如)()())的最长有效长度是 4。这道题用栈时栈里存的不是括号本身而是下标并且初始要把-1放进去作为基准点。遇到)时弹出栈顶然后计算当前下标和栈顶下标的差值这个差就是当前连续有效的长度。它和“有效的括号”题的关系在于判断有效括号的位置是连续的而“连续”需要用下标差值来量化。做完基础题后再去刷新题对栈的理解会完全不同。5.3 带通配符的括号匹配从确定性到贪心有些扩展题会让字符串里出现*它可以被当作左括号、右括号或者空字符问是否能形成有效括号序列。这种问题可以引入两个栈分别记录左括号和星号的下标也可以使用贪心算法维护一个未匹配左括号的数量区间。它不再要求严格的最近匹配因为*给了你“变通”的可能。做这道题时你会重新反思标准栈解法里“必须弹出栈顶”的规则原来只是多种可能性中最严格的一种。5.4 栈在解析场景中的迁移括号匹配只是栈应用的一个缩影。LeetCode 第 71 题“简化路径”也会用到栈把路径按/切分遇到..弹出栈顶遇到普通目录名入栈最后拼接返回。核心还是“处理当前项时要回顾最近的一项”。你如果能把 20、22、32、71 这四题串起来看会发现它们都在处理同一个母题如何用栈维护“最近上下文”。6. 从能 AC 到面试能讲我的刷题心得与练习顺序6.1 刷题过程中最容易写的三个 Bug第一个 Bug 是忘记最后检查栈空只判断遍历过程不报错就返回 True导致(((被误判为有效。第二个 Bug 是遇到右括号时先return False再弹出栈顶导致左右数量匹配但顺序正确的字符串也失败。第三个 Bug 是stack[-1]在栈空时取不到元素Python 会抛IndexError有些语言返回未定义行为。这三个问题在面试手写时特别容易暴露因为面试官会不断给你边界用例。排查技巧很简单写完后用四组用例自测。应返回 True。]应返回 False。((应返回 False。([)]应返回 False。如果代码能一次性通过这四种基本用例再跑 LeetCode 的提交用例就稳了。6.2 从写对代码到讲清楚思路面试时不要上来就写代码。我一般会先说“这个问题的核心是括号的匹配具有后进先出特性所以我会用栈。遇到左括号入栈遇到右括号检查栈顶如果类型不匹配或栈为空则无效遍历完毕后栈必须为空。”这个回答把数据结构选择和算法流程一次说清比闷头写代码加分很多。之后如果面试官追问“为什么不用计数器”你可以回答“计数器无法区分括号类型之间的顺序关系比如([)]会让计数器归零但实际无效”。这个追问几乎是必问提前准备就不会慌。6.3 练习路径建议如果你刚开始刷题我建议按这个顺序来第 20 题“有效的括号”打底理解栈的入栈、弹栈、栈顶判断。第 22 题“括号生成”加深对括号序列结构的理解练习回溯。第 32 题“最长有效括号”练习栈存下标、动态规划两种思路有一定难度。第 71 题“简化路径”换一个场景用栈确认自己不是只会背括号题。每道题之间间隔一天不要同一天连做四题否则容易混淆。做完每题后尝试不看代码再写一遍直到能在五分钟左右流畅完成。6.4 关于这道题我最后想多说一句这题我已经写了不下二十遍但每次讲给不同水平的人听都会发现新的表达方式。给初学者讲我会把栈比喻成“一叠盘子”最近的盘子必须先拿走给工作多年的工程师讲我会直接说“这就是编译原理里的词法分析基础”。你掌握的程度取决于你能用多少种方式解释它。如果你觉得已经会了不妨尝试不借助任何变量名提示只凭脑中推演完成代码这个训练对面试手写帮助很大。