每天一题今天轮到了“有效的括号”。这道题在力扣上编号是 20标签是“栈”难度写着“简单”。但“简单”只是对已经掌握栈的人才成立的。我拿它问过不少人十个里有三四个会在([)]这个用例上栽跟头。原因不是没听过“括号匹配”这四个字而是把“有效括号”偷换成了“左右括号数量相等”。等真正一跑才发现括号匹配是一个结构问题不是计数问题。这篇笔记想把它完整拆一遍题目到底在判断什么为什么栈天生适合干这件事用 Python、JavaScript、Java 写出来的代码有什么不一样的讲究刷的过程中最容易踩哪几个坑搞清楚之后又能顺带连出哪些相关题目适合三类人看准备算法面试的求职者、正在补数据结构基础的学生、以及像我一样把每日一题当日常训练的老码农。1. 先把“有效括号”这五个字的隐藏条件读透题目原文其实很直白给定一个只包含(、)、{、}、[、]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有一个对应的相同类型的左括号。官方给的几个例子里()、()[]{}、{[]}都是 true(]是 false。但真正容易忽略的是([)]我第一次刷这题就在它上面掉了链子统计一下(和)各一个[和]各一个数量完全平衡为什么会 false因为条件 2 里写的“正确的顺序”并没有被数量条件覆盖。([)]的问题在于(还没闭合就开了[而第一个右括号)出现时离它最近的未闭合左括号是[不是(。两对括号交叉着占位像两条绳子打了个结自然不算有效。1.1 “正确的顺序”其实说了两层意思如果把“正确顺序”拆开会发现它其实是两条规则右括号的匹配对象必须是“离它最近的那个未闭合左括号”匹配成功的同时这个左括号的“待闭合状态”才被结清。第一条规定了方向由内向外闭合永远先关最里面的那层括号。第二条则是自然结果。这就是教科书里常说的“就近匹配”。一旦接受了这个规则{[]}有效、([)]无效都是顺理成章的事。再往深一层看括号匹配本质上描述了一种树形结构。把每一对匹配括号看作一个节点嵌套关系就是父子关系平铺关系就是兄弟关系。{[()]}是四层嵌套的树()[]{}是三棵独立的树并列而交叉的([)]就像两个家族的孩子互相换位画出来全是交叉线——这在树里不合法。理解这层树形思维有个实际好处后面刷“括号生成”“最长有效括号”这类题时你会不自觉地把括号序列跟树的遍历对应起来解题思路会清晰很多。1.2 为什么这题是计算机领域的基础题括号匹配不是面试官从题库里随手挑的偏题它是编译原理、甚至整个程序世界里最底层的“语法正确性检查”之一。编译器在词法和语法分析阶段需要检查代码块{}的配对是否完整现在的代码编辑器能做括号高亮、自动缩进背后就是“校验括号配对是否合法”HTML/XML 里标签的嵌套本质上也是一对“广义括号”div对应/div就连 JSON 校验器检查的也是花括号、方括号之间的配对完整。所以“有效的括号”不是一道孤立的题它是这些工程能力的一个最小演示单元。把这一题吃透等于把“用栈处理嵌套结构问题”的通用模型装进了脑子里。2. 从暴力尝试到栈解法两条翻车思路与正确推演2.1 先聊大家容易想到的两个方案为什么都不行第一个方案是计数器。只关心左右括号数量维护一个count遇到左括号 1右括号 -1最后看count是否为零。对单一种类括号比如只有()这个方案是成立的但在三种括号混排时([)]这种输入会让计数归零却判成有效。显然不行。第二个方案是“字符串化简”反复删除相邻的完整括号对直到删不动为止。伪代码大概长这样def is_valid_naive(s: str) - bool: while () in s or [] in s or {} in s: s s.replace((), ).replace([], ).replace({}, ) return s 这个方案如果循环到删不动结论其实是对的但有两个问题。第一是复杂度最坏情况下要扫描字符串 O(n) 次每轮的多次替换又是 O(n)整体 O(n^2)遇到很长的嵌套输入会超时。第二是它掩盖了真正的模型看起来是在“化简字符串”实际上能删空的原因恰恰是这些括号对“可以消去”——这背后就是栈模型。面试官如果顺着追问一句“为什么能删空”你最终还是得回到栈来解释。我见过不止一个候选人在现场写这个方案然后自信地说“这是 O(n)”其实不是。设计题解的时候复杂度一定要自己算清楚不能凭感觉。2.2 栈的进出规则只有四条回到正题。用栈解决这个问题规则简单到只用记住四条遇到左括号(、[、{压入栈顶遇到右括号)、]、}先看栈顶栈顶与当前右括号类型匹配则弹出栈顶不匹配或栈为空直接返回 false遍历完整个字符串后栈必须是空的否则还有左括号没闭合返回 false。这四条规则里最容易忘的是第 4 条。很多人写完代码拿(((一跑就露馅了——字符串扫完了栈里还压着三个(当然不算有效。2.3 用两组例子推演{[]} 和 ([)]光说规则不够直观我手写一遍过程。拿{[]}走一遍当前字符操作栈内容{push 入栈[ { ][push 入栈[ {, [ ]]peek 栈顶是[匹配pop[ { ]}peek 栈顶是{匹配pop[ ]遍历结束栈空返回 true。再拿([)]走一遍当前字符操作栈内容(push 入栈[ ( ][push 入栈[ (, [ ])peek 栈顶是[不匹配直接返回 false两行就出结果。注意我们根本没有往后扫描一个右括号一旦发现栈顶对不上整串就不可能有效了后面的字符不用再看。这也是栈最大的优势你永远只需要看“最近”的那个未闭合左括号前面的历史都被压缩在栈里。每一层括号就像一摞盘子拿走的永远是最上面那块。2.4 复杂度为什么要说“摊销 O(1)”栈解法的时间复杂度是 O(n)因为每个字符最多入栈一次、出栈一次。空间复杂度最坏是 O(n)比如输入是((((((((这种全是左括号的情况栈里要存全部字符。至于某些语言里append/pop为什么说“摊销 O(1)”是因为底层数组扩容时偶尔要整体搬家但平均下来每次操作就是常数时间。面试时能说出“摊销”这个词会显得你对底层实现有了解。3. 代码落地三种语言三种容器风格先上一个总思路在三种语言里都做同一件事——用字典保存右括号到左括号的映射遇到右括号时查表遇到左括号时入栈。之所以把右括号当 key是因为判断时的主角色是右括号它一出现就要立刻找对象而对象就是栈顶栈顶一定是个左括号。3.1 Pythondict list最短却也最容易写错Python 版本代码很短def isValid(s: str) - bool: if len(s) % 2 1: return False pairs { ): (, ]: [, }: {, } stack [] for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack三个细节提醒一下len(s) % 2 1直接剪枝左右括号必须成对长度是基数直接不合法。这是一个 O(1) 的小优化说出了会让面试官觉得你读题仔细。判断顺序必须是not stack or stack[-1] ! pairs[ch]先判空再判顶否则空栈取stack[-1]会抛 IndexError。return not stack比return len(stack) 0更 Pythonic不过后者语义更一目了然两种写法都行。3.2 JavaScript数组天然就是栈JS 里没有专门的 Stack 类但 Array 的 push/pop 就是栈的基本操作所以直接拿数组当栈用var isValid function(s) { if (s.length % 2 1) return false; const pairs { ): (, ]: [, }: { }; const stack []; for (const ch of s) { if (pairs[ch]) { if (stack.length 0 || stack[stack.length - 1] ! pairs[ch]) { return false; } stack.pop(); } else { stack.push(ch); } } return stack.length 0; };有一点容易踩坑在 JS 里判断“当前字符是不是右括号”不要下意识写pairs.hasOwnProperty(ch)。用if (pairs[ch])就行因为 map 的 key 只有右括号左括号查出来是 undefined会走 else 分支。也可以用if (ch in pairs)语义更明确两者都不算错。重点是别把pairs的 key 定义成左括号否则判断逻辑整个要反着写容易把自己绕晕。3.3 Java为什么我推荐 ArrayDeque 而不是 StackJava 面试时容器选择是个高频追问点。很多初学者一上来用Stack这个类的问题在于它继承自Vector每个方法都带synchronized同步锁在单线程刷题场景属于多余开销。更好的选择是ArrayDeque数组实现的双端队列push/pop/peek 都没有锁性能更好。class Solution { public boolean isValid(String s) { if (s.length() % 2 1) { return false; } MapCharacter, Character pairs Map.of(), (, ], [, }, {); DequeCharacter stack new ArrayDeque(); for (char ch : s.toCharArray()) { if (pairs.containsKey(ch)) { if (stack.isEmpty() || stack.peek() ! pairs.get(ch)) { return false; } stack.pop(); } else { stack.push(ch); } } return stack.isEmpty(); } }这里有两个小点Map.of(...)是 Java 9 以后才有的力扣现在的 Java 环境完全支持。如果不确定版本改成HashMap加三个 put 也完全可以。Deque接口下的push是头插pop是头节点弹出peek是查看头节点。ArrayDeque虽然叫双端队列用这几个方法时它就是标准栈。面试官如果问“Stack 和 ArrayDeque 都能实现栈有什么区别”把 synchronized 和 Vector 那套话说出来就够加分了。3.4 三个版本的对照语言栈容器取栈顶写法弹栈写法备注Pythonliststack[-1]stack.pop()语言原生最轻量JavaScriptArraystack[stack.length - 1]stack.pop()数组天然支持JavaArrayDequestack.peek()stack.pop()避免用 Stack 类三种语言容器形态不同但核心思想完全一致右括号驱动判断左括号等待出栈。背代码不如背这个流程。4. 六个易错点与一套反例驱动的自测用例4.1 六个坑逐个看漏掉“遍历完栈要为空”。(((、((()))(这种输入如果只匹配不检查栈空整个函数会错误返回 true。这一条排在坑位第一因为它是新手最常见、也最好修的一个错误加上一行return stack.isEmpty()就好但很多人就是忘。右括号出现时栈已经为空。比如())第二个)出现时栈是空的stack[-1]直接崩溃。所以每次遇到右括号必须先把“栈空”当成不合法来对待。只数数量、不区分类型。计数器方案在单括号类型下可行三种括号混排就废了([)]是它的天然反例。字典映射方向写反。如果 map 定义成{ ( : )}你会发现判断时要先取栈顶、再去查表逻辑拧巴还容易漏判。我的习惯是统一右括号 - 左括号这样“遇到右括号查它该配谁”的语义和代码一一对应。先 pop 再比较。有人为了省一行写成if (stack.pop() ! pairs[ch]) return false;。这在栈空时会抛异常在栈顶不匹配时信息也丢失了。正确流程永远是先 peek 看再决定 pop 不 pop。用字符串替换法硬刚长输入。前面讲过它能得到正确结论但效率不够面试现场用很容易被追问到复杂度然后露怯。4.2 一套建议自测用例刷题不能只测 sample case我习惯把用例分成四组合法、非法、边界、压力。这里列一份可以直接用的清单输入预期测什么true空串边界()true最小合法()[]{}true平铺多种括号{[]}true多层嵌套((()))true深嵌套同类型(]false类型不匹配([)]false交叉嵌套(((false只有左括号)))false只有右括号(()false左右数量都不等({[})false部分交叉如果你在自己电脑上跑这组用例十一个全过这道题基本上就稳了。4.3 反例驱动的测试思维这组用例背后的方法论比用例本身更有用永远给每个条件配一个反例。“左括号必须类型匹配”——反例(]“顺序正确闭合”——反例([)]“每个右括号都有对应左括号”——反例())“遍历完必须栈空”——反例(((“栈空时遇到右括号”——反例)。你会发现有效括号的每一条判定规则几乎都能用一个一两个字符的字符串把它逼到墙角。养成这个“反例驱动”的习惯面试时提测试用例会比你背二十个 happy path 从容得多。5. 这题之外括号问题家族与栈的真实应用5.1 力扣上一串括号题“有效的括号”只是括号家族的入口。顺着这条线刷下去你会发现括号题几乎覆盖了算法基础里不少重要技巧题号题名难度核心思路一句话20有效的括号简单栈匹配栈空判断22括号生成中等回溯左右括号计数32最长有效括号困难栈存下标 / 动态规划678有效的括号字符串中等双栈或贪心放缩区间856括号的分数中等栈维护累加分数921使括号有效的最少添加中等贪心缺多少补多少1249移除无效的括号中等栈标记非法下标再删除394字符串解码中等数字栈 字符栈刷完 20 题再看 394 题“字符串解码”你会更容易理解为什么需要“数字栈”和“字符串栈”两个栈搭配因为嵌套结构里每一层的“重复次数”和“已拼接字符”是两层独立状态。5.2 栈在真实工程里会出现在哪些地方除了面试题栈几乎是软件系统里默认的“嵌套状态管理器”。举几个日常写代码会遇到的真实场景函数调用栈每个函数调用压一帧返回时弹一帧和括号匹配一模一样代码编辑器实现括号自动配对、高亮不匹配的括号HTML 解析器/浏览器引擎解析div嵌套到/div本质就是广义括号对JSON 或 XML 的格式校验器花括号、方括号之间的配对检查编译器里的表达式求值中缀转后缀表达式要靠运算符栈撤销/重做Undo/Redo历史操作记录其实就是栈。你会发现括号匹配不是一道孤独的题它是“用栈处理嵌套结构”这个通用模型的种子。种植这颗种子最好的方式就是把今天这题亲手写一遍、debug 一遍、再把反例跑一遍。5.3 把今天的思路再抽象一点如果只能从这题带走一样东西我的建议是带走这个意识凡是“嵌套”“最近”“上下文相关”这三类词同时出现栈都是第一个值得考虑的数据结构。括号匹配是嵌套函数调用是嵌套HTML 标签是嵌套甚至做 JSON 解析时遇到的“当前在哪个对象里”本质也还是嵌套。栈的作用就是记住一个“未完成列表”然后逆序结账——这就是后进先出的全部意义。最后聊点私人的东西。我拿这道题去问候选人的时候从不要求背代码就问两个问题“栈里存的是什么什么时候弹”能把这两句话说明白的人就算手写不出来我也觉得他是真懂的。反过来能默写出完整代码但说不清这两个问题的人我基本可以断定他是背的。这道题我已经写过不止一百遍了每次写还是会把空栈判断放在最前面。它不是玄学是逻辑顺序和肌肉记忆的结合。希望你今天看完也去编辑器里亲手敲一遍用那十一组用例喂它一次感受一下([)]被一个栈顶就拦下来的瞬间。