1. 这道简单题为什么能挂掉一半候选人1.1 题目回顾三个硬规则LeetCode第20题有效的括号在题库里的难度标记是简单但真实面试中它的杀伤力一点都不小。题目要求很简单给定一个只包含(、)、{、}、[、]的字符串判断它是否是有效的括号字符串。有效需要同时满足三个条件左括号必须用相同类型的右括号闭合也就是说(只能由)关闭不能拿去和]配对。左括号必须以正确的顺序闭合这要求括号之间要么平行排列要么完全嵌套不能交叉。每个右括号都有一个对应的相同类型的左括号这个条件强调的是一一对应关系。把三条规则翻译成人话就是()[]{}、({[]})都是有效的而(]、([)]、())都是无效的。尤其要注意([)]这个经典反例。它每种括号的数量都匹配一个(对应一个)一个[对应一个]按数量来看完全没问题但它却是无效的。原因是第二个字符[在第一个字符(还没关闭之前就插了进来括号结构变成了交叉而不是嵌套。括号匹配要求最内层必须先关闭后打开的先关闭形成一层套一层的洋葱结构。1.2 面试官真正想从这道题里看到什么这道题在面试中出现频率极高的原因恰恰是因为它简单。面试官用一道简单题能在很短时间里看出候选人三件事。第一基础coding能力。字符串遍历、条件判断、数据结构选择这些基本功在简单题面前无处遁形。第二边界意识。栈空的时候能不能想到判空遍历完栈里还有残留在不在考虑范围内字符串长度为奇数是否值得提前剪枝第三对数据结构的理解深度。很多人背过解法知道要用栈但被追问一句为什么用栈而不是队列就答不上来。我还在一些模拟面试里见过候选人用计数法处理三种括号遇到([)]直接返回 true这就是不理解栈的核心价值。所以说这道题是简单题的外表考功底的里子。另外一个隐藏考察点是对复杂度分析的熟练度。就算写对了栈解法面试官大概率还会追一句时间复杂度多少空间复杂度多少能不能优化如果只背了代码没有想通原理这种追问很容易卡壳。这也正是我写这篇文章的原因。下面五种方案分别是栈加哈希表的标准解法、数组模拟栈的改良解法、递归消除法、替换消除法、计数器法。每一种我都会讲清楚原理、代码、适用场景和踩坑点这样不管是应付面试还是自己刷题都能做到心里有数。2. 方案一栈加哈希表教科书都在用的标准答案2.1 为什么栈和括号匹配是天生一对先回答那个面试官最常追问的问题为什么这道题要用栈括号匹配的本质是后进先出。看这个字符串({[]})先出现(再出现{再出现[。关闭时顺序刚好反过来先关]再关}最后关)。最晚出现的左括号最先被匹配这正是栈的行为特征。用一个生活化的场景来理解想象一摞盘子你每次往上面放一个新盘子取的时候只能从最上面拿。括号字符串扫描到每个左括号时就相当于是放一个盘子上去遇到右括号时要检查的那个左括号一定是最近放上去的那个盘子。如果这个盘子和右括号类型不匹配或者盘子已经拿光了却还有右括号进来那这个字符串必然是无效的。理解了这一层再看代码就顺理成章了扫描整个字符串遇到左括号入栈暂存遇到右括号从栈顶弹出一个左括号来配对能配上就继续配不上或者栈空了就直接判 false。2.2 完整实现与三个关键边界直接给一份可以跑通的 Java 实现public boolean isValid(String s) { if (s null || s.length() % 2 1) { return false; } MapCharacter, Character pairs new HashMap(); pairs.put(), (); pairs.put(], [); pairs.put(}, {); 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(); }这段代码有几个值得展开讲的细节。第一个边界字符串长度为奇数时直接返回 false。因为有效括号串必须成对出现奇数长度一定无效。这个剪枝在面试里主动提出来是很加分的细节。第二个边界遇到右括号时栈可能是空的。比如输入字符串是)(扫到第一个字符)时栈里什么都没有这时就没法配对直接 false。很多人写这道题的时候忘了判空调起来又慢又折磨。第三个边界遍历完整个字符串后栈必须是空的。比如(()扫到最后栈里还残留一个(这说明有一个左括号始终没等到它的右括号字符串无效。另外为什么用Deque而不是 Java 的Stack因为Stack继承自Vector所有方法都加了同步锁性能差而且官方已经不推荐使用了。ArrayDeque是纯数组实现没有同步开销做栈用更合适。Map 的映射方向是右括号 - 左括号这样设计的好处是扫描到右括号时可以直接查出它期待匹配的左括号类型。如果方向反了遇到左括号还要去查它对应的右括号是什么代码逻辑会绕很多。2.3 复杂度分析与一个简洁的 Python 版本时间复杂度是 O(n)每个字符最多入栈一次、出栈一次空间复杂度是 O(n)最坏情况是输入全为左括号比如((((((((栈里需要存 n/2 个字符。这个复杂度已经是本题的最优解因为至少需要扫描一遍字符串才能判断所有括号所以不可能低于 O(n)。顺手给 Python 读者一个更简洁的版本class Solution: def isValid(self, s: str) - bool: 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逻辑完全一样只是 Python 的 list 天然可以当栈用append对应入栈pop对应出栈stack[-1]对应查看栈顶。方案一的定位是标准答案因为它在正确性、可读性、复杂度之间取得了最好的平衡。面试时第一个给这个方案基本不会错。3. 方案二数组模拟栈被追问能不能不用栈时的答案3.1 为什么需要自己造一个栈如果你把方案一写完面试官可能会顺着你的代码继续问几个问题ArrayDeque底层是怎么实现的它会不会扩容性能开销在哪里如果不用现成的栈结构你能不能实现一个这些问题背后的潜台词是面试官想知道你是背过这道题还是真正理解栈的运作机制。系统栈无论是Stack还是ArrayDeque底层是数组超过容量时要扩容、搬迁元素这涉及额外的时间开销。但在有效的括号这道题里输入字符串的长度是已知的栈的最大深度在开始之前就能估算出来完全可以一次性把容量开够。这样既省去了扩容调整也让面试官知道你对栈的底层实现有概念。另外手写数组栈还能避开 JavaStack的同步锁问题也避开ArrayDeque在某些面试场景下无法使用的问题比如面试官要求不能用任何现成集合类只能用基本数组。3.2 数组加 top 指针的核心实现public boolean isValid(String s) { if (s null || s.length() % 2 1) { return false; } char[] stack new char[s.length()]; int top -1; for (char ch : s.toCharArray()) { if (ch ( || ch [ || ch {) { stack[top] ch; } else { if (top -1) { return false; } char left stack[top]; if ((ch ) left ! () || (ch ] left ! [) || (ch } left ! {)) { return false; } top--; } } return top -1; }这里最核心的变量是top它充当栈顶指针。初始值设为 -1表示空栈压入一个元素时先top再赋值弹出元素时直接top--查看栈顶就是stack[top]。这三个操作对应了系统栈的push、pop、peek。有几个容易踩的细节。栈数组的容量直接初始化为s.length()。即使输入全是左括号栈的最大深度也就是 n不会越界。有人会写成s.length() / 2 1因为有效括号串的左括号数量最多是总长度的一半。这个优化可以做但意义不大反而增加了思考成本面试时我建议直接用s.length()省心且绝对不会越界。top -1是判空条件不是top 0。这是新手最容易搞混淆的地方。当栈里还有一个元素时 top 为 0如果写成top 0判空会把栈底的元素误判成空。匹配判断时我用了一个相对朴素的写法拿到栈顶的左括号 left再看当前右括号 ch 是否和 left 匹配。这样写虽然长一点但逻辑非常透明每一步在干什么都清清楚楚。3.3 什么时候该给这个方案数组模拟栈的时间复杂度和空间复杂度都与方案一相同都是 O(n) 时间、O(n) 空间但实际运行时的常数更小因为省掉了对象创建、扩容检查等开销。不过这并不意味着你要在面试一开始就写它。我见过一些候选人上来就手写数组栈写得很辛苦面试官却觉得他太套路化。更自然的节奏是先用方案一的代码拿到正确性等面试官追问能不能不用现成栈时再切到方案二并且主动解释一句因为输入长度已知数组容量可以一次开满避免了动态扩容的开销。这样说出口面试官会觉得你不仅会做题还懂工程实现里的性能取舍。4. 方案三递归消除法每一次吞掉一对相邻匹配4.1 从问题结构看递归的切入点栈解法是从左到右扫描字符串边走边记。递归消除法换了一个完全不同的视角不断消除字符串中已经匹配的括号对看最终能不能把整个字符串消成空串。先说一个规律任何一个有效的括号字符串必然至少有一对相邻的、可直接匹配的括号。比如()[]中的()和[]({[]})中的[]。把这个规律反过来用就是递归消除法的核心思路找到字符串里第一对相邻匹配的括号把它删掉然后递归判断剩下的字符串是否有效。如果整个字符串能被一步一步消成空串那它就是有效的。这个过程很像消消乐。每次找到可以消除的两个相邻字符删除后原本不相邻的字符会重新靠在一起可能会形成新的可消除配对于是继续消直到消不动为止。例如({[]})的消除过程是先找到[]删除后变成({})再找到{}删除后变成()最后找到()删除后变成空串判定有效。4.2 递归实现与递归深度隐患按照这个思路可以写出这样的代码public boolean isValid(String s) { if (s.length() 0) { return true; } for (int i 0; i s.length() - 1; i) { String pair s.substring(i, i 2); if (isMatchedPair(pair)) { String next s.substring(0, i) s.substring(i 2); return isValid(next); } } return false; } private boolean isMatchedPair(String pair) { return ().equals(pair) || [].equals(pair) || {}.equals(pair); }递归的终止条件有两个一是字符串被消成空串说明所有括号都能正确配对返回 true二是遍历完所有相邻的两个字符找不到任何一对可匹配的括号同时字符串又不是空串说明有无法消除的残留返回 false。这段代码能过 LeetCode 的测试但它的性能并不理想。每次调用substring拼接新字符串都是 O(n) 操作而最坏情况下需要递归 n/2 层所以综合复杂度是 O(n^2)。空间上递归栈的深度同样可能达到 O(n)极端情况下还会触发栈溢出。说实话这个方案面试时不建议作为主答案但如果你能讲出这个思路再主动补一句它虽然直观但字符串拼接带来 O(n^2) 的复杂度所以工程上不会用面试官反而会看到你的思路广度和复杂度敏感度。5. 方案四替换消除法最直观但最容易翻车的思路5.1 循环替换到不再变化替换消除法和递归消除法的思路一脉相承但实现方式更暴力直接用字符串替换把所有的()、[]、{}一次性换成空字符串然后看还能不能继续替换直到字符串不再变化。public boolean isValid(String s) { while (s.contains(()) || s.contains([]) || s.contains({})) { s s.replace((), ).replace([], ).replace({}, ); } return s.isEmpty(); }整个过程就像反复给字符串剥洋葱外层剥掉一层内层暴露出来下一轮再剥直到剥完或者剥不动为止。这个思路的正确性其实是有保障的。每一步消除的都是当前字符串中可以直接闭合的最小括号对而这种括号对在一个有效括号串里一定存在。持续消除后有效串会变成空串无效串会留下无法消除的残留字符。在 LeetCode 的测试数据规模下它也能通过代码极短一眼就能看懂。如果你是在一个不追求性能的业务场景里临时校验括号这样写是最省事的。5.2 它的性能问题与隐藏的雷替换消除法最大的问题是性能。String.replace每次调用都会完整扫描一遍字符串并生成新的字符串对象。假设字符串有 n 层嵌套每轮至少消除一层最坏需要 O(n) 轮每轮 O(n) 扫描综合时间复杂度是 O(n^2)。如果嵌套特别深这个开销是实打实的。还有一个容易被忽略的坑replace方法底层要处理字符匹配和数组复制连续调用三次replace时上一轮刚生成的新字符串又会被下一轮replace全量扫描一遍。明明只消掉几个字符却把整串重新复制了好几次非常不划算。如果换成正则表达式replaceAll就更慢了正则匹配本身有额外的编译和执行开销而且还得小心翼翼地处理括号的转义字符完全没有必要。所以我的结论是方案四适合作为想证明自己思路开阔时的补充但绝对不要把它当成正式答案。面试官如果追问它的复杂度你最好能脱口而出 O(n^2)并且能说出因为它每轮只消除一层嵌套需要反复扫描这样的原因。这样哪怕你不推荐这个方案面试官也知道你不是不懂只是做了取舍。6. 方案五计数器法作为反例反而能讲清楚栈的必要性6.1 在单一类型括号下计数是可行的假设题目退化成最简单的情况字符串里只有(和)两种字符判断括号是否有有效。这时候完全不需要栈一个计数器就够了。public boolean isValid(String s) { int count 0; for (char ch : s.toCharArray()) { if (ch () { count; } else { count--; if (count 0) { return false; } } } return count 0; }逻辑非常直白遇到(加一遇到)减一任何时候计数器变成负数说明)多出来了直接失败遍历完计数器必须归零否则说明有(没有匹配。这个方案的时间复杂度是 O(n)空间复杂度是 O(1)在三种括号场景下是不可能做到的。但如果题目只涉及一种括号它就是最优解连栈都不需要。6.2 为什么([)]让计数器彻底失效一旦括号类型增加到三种计数器方案就崩了。问题不在于计数器能不能统计数量而在于它丢失了顺序和类型两个关键信息。看一个例子([)]。按计数器方案统计左括号数量是 2右括号数量也是 2最终数量和类型都能对上会误判为有效。但这个字符串实际上是无效的因为它不是一个合法的括号嵌套结构。用图示能看得很清楚(期待的是)但[插在两者之间[期待的是]但显然)出现时最内层还没有关闭。这种交叉嵌套在视觉上表现为括号线交叉在结构上是完全非法的。为什么栈能解决这个问题因为栈不仅保存了有哪些左括号还没匹配还保存了它们的出现顺序。当遇到一个右括号时栈顶就是当前最近、最应该被匹配的左括号。如果最内层的期待类型不匹配整个字符串就无效。计数器只有数量没有先后顺序自然无法判断这种情况。所以计数器法在三种括号的场景下更多是作为一个反例存在。面试时你可以主动提这么一句如果只有一种括号O(1) 空间的计数器就行但多类型时不行因为我们需要保留顺序信息所以栈是必要的。这句话会让面试官意识到你不仅知道怎么做还知道为什么要这样做以及不同方案之间的边界在哪里。7. 五种方案横向对比以及面试时到底该先讲哪个7.1 复杂度与代码量对比五种方案的取舍放到一张表里看最清楚方案平均时间复杂度空间复杂度代码量面试推荐度栈 哈希表O(n)O(n)短首选数组模拟栈O(n)O(n)稍长追问时展示递归消除法O(n^2)O(n) 递归栈短思路补充替换消除法O(n^2) 最坏O(n)最短不推荐计数器法O(n)O(1)最短仅限单一括号场景这里有一个经常被搞混的细节递归消除法和替换消除法都不能简单地说空间复杂度是 O(1)。递归消除法的递归调用会占用调用栈空间替换消除法则因为不断生成新的字符串每次替换都占用新内存。只有计数器法真正做到了 O(1) 空间。时间复杂度方面栈解法和数组模拟栈都是线性时间已经是最优解。递归消除法和替换消除法虽然在小数据量下跑得也很快但数据规模一大O(n^2) 的开销会明显暴露。7.2 一套稳妥的答题顺序聊了这么多方案最后给一个可以直接照抄的面试策略。核心原则是先稳后秀先用最常规的方案拿到分再用补充信息展示深度。我的建议是这样的节奏第一步结论先行。直接说这道题可以用栈来解决核心是左括号入栈、右括号弹栈并检查匹配。第二步讲边界。主动提到字符串长度为奇数、遍历到右括号时栈为空、遍历结束后栈不为空这三点。把边界讲清楚比机械地写代码更能体现你的严谨。第三步写方案一。代码短、可读性高、复杂度最优这是最稳妥的答案。第四步如果面试官追问能不能不用现成栈切到方案二顺便讲一句输入长度已知数组容量可以一次开满避免动态扩容。第五步如果面试官追问还有没有其他思路聊递归消除法或替换消除法但一定要主动补一句它们时间复杂度退化到 O(n^2)所以工程上不常用。第六步只有在下班后面试官想闲聊或者这是一道开放性问题时再聊计数器法。正常面试中计数器法更适合在讲完栈解法之后作为为什么用栈的反面论证来提一嘴而不是单独作为一个答案。五个方案全部往外倒是最容易翻车的面试官会觉得你没有重点抓不住主次。一次面试不需要展示所有解法只需要展示出你能在最合适的时机给出最合适的答案。8. 题目之外两道变体题与生产环境里的括号匹配8.1 变体题一最长有效括号LeetCode 第 32 题最长有效括号是在 #20 的基础上做文章不是判断整个字符串是否有效而是找出最长的有效括号子串的长度。这道题用栈也能做但技巧性更强。需要在栈底预先放一个-1作为哨兵用来标记最后一个未匹配右括号的位置。具体来说遇到(就入栈入栈的是当前索引遇到)就出栈如果出栈后栈为空说明当前右括号没有匹配的左括号把它作为新的哨兵压入栈如果出栈后栈不为空说明从栈顶索引的下一个位置到当前位置是一段有效子串用i - stack.peek()更新答案。这个思路和 #20 的栈解法一脉相承区别在于 #20 遇到栈空时直接判定无效而 #32 遇到栈空时把这当作一段有效区间的起点记录下来。一个细微的差别解决的问题就从是否有效变成了最长有效长度是多少。8.2 变体题二删除无效的括号LeetCode 第 301 题删除无效的括号要求删除最少数量的括号使得整个字符串变成有效的括号字符串。这道题一般用 BFS 或者回溯而判断某个候选字符串是否有效背后调用的正是今天这道题的判断逻辑。如果用 BFS 来做每一层枚举删除一个括号后的所有可能字符串然后用一个isValid来判断每个候选串是否有效第一个合法结果就是答案。isValid内部实现就是我们前面讲过的栈解法。那本题的某个方案会被当作其他题目里的一个子模块反复调用。这也是刷题的价值——很多题看起来是新的底层缝缝补补用的都是最常见的那几个原语。有效的括号就是原语之一。8.3 生产环境里的括号匹配抛开考试和刷题括号匹配在真实工程里的应用比我最初预想的要广得多。编译器方向各种语言的表达式解析都要检查括号是否配对、嵌套层级是否合法。一个简单的递归下降解析器核心逻辑就是不断匹配左括号和右括号。代码编辑器方向括号高亮和自动补全功能也需要在输入每个字符时判断当前括号栈的状态([{的亮色配对本质上就是一个栈的应用。HTML 和 XML 的标签校验也可以理解为括号匹配的变体只是标签名代替了(和)。表达式求值系统里中缀表达式转后缀表达式、计算器处理括号优先级背后同样是栈在支撑。可以说括号匹配是整个结构化文本处理的基础模块。所以这道题真正训练的其实是一种识别嵌套结构的能力。这种能力一旦建立你再去看递归下降、JSON 解析、模板引擎、Tag 配对这类问题都会有这题我见过的感觉。最后分享一个我刷题多年的个人习惯拿到一道题尽量逼自己写至少三种解法哪怕其中两种是不推荐的。因为第一种解法让你会做第二种解法让你看穿本质第三种解法让你知道边界。这道 #20 特别适合用来做这个训练因为它足够简单可以把所有注意力都放在为什么上而不是被复杂的业务逻辑绕晕。等你把五种方案都吃透了再去碰 #32、#301、#22 这些括号家族的其他成员会发现一路顺畅。
有效的括号：从栈数据结构到五种解法的深度解析
1. 这道简单题为什么能挂掉一半候选人1.1 题目回顾三个硬规则LeetCode第20题有效的括号在题库里的难度标记是简单但真实面试中它的杀伤力一点都不小。题目要求很简单给定一个只包含(、)、{、}、[、]的字符串判断它是否是有效的括号字符串。有效需要同时满足三个条件左括号必须用相同类型的右括号闭合也就是说(只能由)关闭不能拿去和]配对。左括号必须以正确的顺序闭合这要求括号之间要么平行排列要么完全嵌套不能交叉。每个右括号都有一个对应的相同类型的左括号这个条件强调的是一一对应关系。把三条规则翻译成人话就是()[]{}、({[]})都是有效的而(]、([)]、())都是无效的。尤其要注意([)]这个经典反例。它每种括号的数量都匹配一个(对应一个)一个[对应一个]按数量来看完全没问题但它却是无效的。原因是第二个字符[在第一个字符(还没关闭之前就插了进来括号结构变成了交叉而不是嵌套。括号匹配要求最内层必须先关闭后打开的先关闭形成一层套一层的洋葱结构。1.2 面试官真正想从这道题里看到什么这道题在面试中出现频率极高的原因恰恰是因为它简单。面试官用一道简单题能在很短时间里看出候选人三件事。第一基础coding能力。字符串遍历、条件判断、数据结构选择这些基本功在简单题面前无处遁形。第二边界意识。栈空的时候能不能想到判空遍历完栈里还有残留在不在考虑范围内字符串长度为奇数是否值得提前剪枝第三对数据结构的理解深度。很多人背过解法知道要用栈但被追问一句为什么用栈而不是队列就答不上来。我还在一些模拟面试里见过候选人用计数法处理三种括号遇到([)]直接返回 true这就是不理解栈的核心价值。所以说这道题是简单题的外表考功底的里子。另外一个隐藏考察点是对复杂度分析的熟练度。就算写对了栈解法面试官大概率还会追一句时间复杂度多少空间复杂度多少能不能优化如果只背了代码没有想通原理这种追问很容易卡壳。这也正是我写这篇文章的原因。下面五种方案分别是栈加哈希表的标准解法、数组模拟栈的改良解法、递归消除法、替换消除法、计数器法。每一种我都会讲清楚原理、代码、适用场景和踩坑点这样不管是应付面试还是自己刷题都能做到心里有数。2. 方案一栈加哈希表教科书都在用的标准答案2.1 为什么栈和括号匹配是天生一对先回答那个面试官最常追问的问题为什么这道题要用栈括号匹配的本质是后进先出。看这个字符串({[]})先出现(再出现{再出现[。关闭时顺序刚好反过来先关]再关}最后关)。最晚出现的左括号最先被匹配这正是栈的行为特征。用一个生活化的场景来理解想象一摞盘子你每次往上面放一个新盘子取的时候只能从最上面拿。括号字符串扫描到每个左括号时就相当于是放一个盘子上去遇到右括号时要检查的那个左括号一定是最近放上去的那个盘子。如果这个盘子和右括号类型不匹配或者盘子已经拿光了却还有右括号进来那这个字符串必然是无效的。理解了这一层再看代码就顺理成章了扫描整个字符串遇到左括号入栈暂存遇到右括号从栈顶弹出一个左括号来配对能配上就继续配不上或者栈空了就直接判 false。2.2 完整实现与三个关键边界直接给一份可以跑通的 Java 实现public boolean isValid(String s) { if (s null || s.length() % 2 1) { return false; } MapCharacter, Character pairs new HashMap(); pairs.put(), (); pairs.put(], [); pairs.put(}, {); 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(); }这段代码有几个值得展开讲的细节。第一个边界字符串长度为奇数时直接返回 false。因为有效括号串必须成对出现奇数长度一定无效。这个剪枝在面试里主动提出来是很加分的细节。第二个边界遇到右括号时栈可能是空的。比如输入字符串是)(扫到第一个字符)时栈里什么都没有这时就没法配对直接 false。很多人写这道题的时候忘了判空调起来又慢又折磨。第三个边界遍历完整个字符串后栈必须是空的。比如(()扫到最后栈里还残留一个(这说明有一个左括号始终没等到它的右括号字符串无效。另外为什么用Deque而不是 Java 的Stack因为Stack继承自Vector所有方法都加了同步锁性能差而且官方已经不推荐使用了。ArrayDeque是纯数组实现没有同步开销做栈用更合适。Map 的映射方向是右括号 - 左括号这样设计的好处是扫描到右括号时可以直接查出它期待匹配的左括号类型。如果方向反了遇到左括号还要去查它对应的右括号是什么代码逻辑会绕很多。2.3 复杂度分析与一个简洁的 Python 版本时间复杂度是 O(n)每个字符最多入栈一次、出栈一次空间复杂度是 O(n)最坏情况是输入全为左括号比如((((((((栈里需要存 n/2 个字符。这个复杂度已经是本题的最优解因为至少需要扫描一遍字符串才能判断所有括号所以不可能低于 O(n)。顺手给 Python 读者一个更简洁的版本class Solution: def isValid(self, s: str) - bool: 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逻辑完全一样只是 Python 的 list 天然可以当栈用append对应入栈pop对应出栈stack[-1]对应查看栈顶。方案一的定位是标准答案因为它在正确性、可读性、复杂度之间取得了最好的平衡。面试时第一个给这个方案基本不会错。3. 方案二数组模拟栈被追问能不能不用栈时的答案3.1 为什么需要自己造一个栈如果你把方案一写完面试官可能会顺着你的代码继续问几个问题ArrayDeque底层是怎么实现的它会不会扩容性能开销在哪里如果不用现成的栈结构你能不能实现一个这些问题背后的潜台词是面试官想知道你是背过这道题还是真正理解栈的运作机制。系统栈无论是Stack还是ArrayDeque底层是数组超过容量时要扩容、搬迁元素这涉及额外的时间开销。但在有效的括号这道题里输入字符串的长度是已知的栈的最大深度在开始之前就能估算出来完全可以一次性把容量开够。这样既省去了扩容调整也让面试官知道你对栈的底层实现有概念。另外手写数组栈还能避开 JavaStack的同步锁问题也避开ArrayDeque在某些面试场景下无法使用的问题比如面试官要求不能用任何现成集合类只能用基本数组。3.2 数组加 top 指针的核心实现public boolean isValid(String s) { if (s null || s.length() % 2 1) { return false; } char[] stack new char[s.length()]; int top -1; for (char ch : s.toCharArray()) { if (ch ( || ch [ || ch {) { stack[top] ch; } else { if (top -1) { return false; } char left stack[top]; if ((ch ) left ! () || (ch ] left ! [) || (ch } left ! {)) { return false; } top--; } } return top -1; }这里最核心的变量是top它充当栈顶指针。初始值设为 -1表示空栈压入一个元素时先top再赋值弹出元素时直接top--查看栈顶就是stack[top]。这三个操作对应了系统栈的push、pop、peek。有几个容易踩的细节。栈数组的容量直接初始化为s.length()。即使输入全是左括号栈的最大深度也就是 n不会越界。有人会写成s.length() / 2 1因为有效括号串的左括号数量最多是总长度的一半。这个优化可以做但意义不大反而增加了思考成本面试时我建议直接用s.length()省心且绝对不会越界。top -1是判空条件不是top 0。这是新手最容易搞混淆的地方。当栈里还有一个元素时 top 为 0如果写成top 0判空会把栈底的元素误判成空。匹配判断时我用了一个相对朴素的写法拿到栈顶的左括号 left再看当前右括号 ch 是否和 left 匹配。这样写虽然长一点但逻辑非常透明每一步在干什么都清清楚楚。3.3 什么时候该给这个方案数组模拟栈的时间复杂度和空间复杂度都与方案一相同都是 O(n) 时间、O(n) 空间但实际运行时的常数更小因为省掉了对象创建、扩容检查等开销。不过这并不意味着你要在面试一开始就写它。我见过一些候选人上来就手写数组栈写得很辛苦面试官却觉得他太套路化。更自然的节奏是先用方案一的代码拿到正确性等面试官追问能不能不用现成栈时再切到方案二并且主动解释一句因为输入长度已知数组容量可以一次开满避免了动态扩容的开销。这样说出口面试官会觉得你不仅会做题还懂工程实现里的性能取舍。4. 方案三递归消除法每一次吞掉一对相邻匹配4.1 从问题结构看递归的切入点栈解法是从左到右扫描字符串边走边记。递归消除法换了一个完全不同的视角不断消除字符串中已经匹配的括号对看最终能不能把整个字符串消成空串。先说一个规律任何一个有效的括号字符串必然至少有一对相邻的、可直接匹配的括号。比如()[]中的()和[]({[]})中的[]。把这个规律反过来用就是递归消除法的核心思路找到字符串里第一对相邻匹配的括号把它删掉然后递归判断剩下的字符串是否有效。如果整个字符串能被一步一步消成空串那它就是有效的。这个过程很像消消乐。每次找到可以消除的两个相邻字符删除后原本不相邻的字符会重新靠在一起可能会形成新的可消除配对于是继续消直到消不动为止。例如({[]})的消除过程是先找到[]删除后变成({})再找到{}删除后变成()最后找到()删除后变成空串判定有效。4.2 递归实现与递归深度隐患按照这个思路可以写出这样的代码public boolean isValid(String s) { if (s.length() 0) { return true; } for (int i 0; i s.length() - 1; i) { String pair s.substring(i, i 2); if (isMatchedPair(pair)) { String next s.substring(0, i) s.substring(i 2); return isValid(next); } } return false; } private boolean isMatchedPair(String pair) { return ().equals(pair) || [].equals(pair) || {}.equals(pair); }递归的终止条件有两个一是字符串被消成空串说明所有括号都能正确配对返回 true二是遍历完所有相邻的两个字符找不到任何一对可匹配的括号同时字符串又不是空串说明有无法消除的残留返回 false。这段代码能过 LeetCode 的测试但它的性能并不理想。每次调用substring拼接新字符串都是 O(n) 操作而最坏情况下需要递归 n/2 层所以综合复杂度是 O(n^2)。空间上递归栈的深度同样可能达到 O(n)极端情况下还会触发栈溢出。说实话这个方案面试时不建议作为主答案但如果你能讲出这个思路再主动补一句它虽然直观但字符串拼接带来 O(n^2) 的复杂度所以工程上不会用面试官反而会看到你的思路广度和复杂度敏感度。5. 方案四替换消除法最直观但最容易翻车的思路5.1 循环替换到不再变化替换消除法和递归消除法的思路一脉相承但实现方式更暴力直接用字符串替换把所有的()、[]、{}一次性换成空字符串然后看还能不能继续替换直到字符串不再变化。public boolean isValid(String s) { while (s.contains(()) || s.contains([]) || s.contains({})) { s s.replace((), ).replace([], ).replace({}, ); } return s.isEmpty(); }整个过程就像反复给字符串剥洋葱外层剥掉一层内层暴露出来下一轮再剥直到剥完或者剥不动为止。这个思路的正确性其实是有保障的。每一步消除的都是当前字符串中可以直接闭合的最小括号对而这种括号对在一个有效括号串里一定存在。持续消除后有效串会变成空串无效串会留下无法消除的残留字符。在 LeetCode 的测试数据规模下它也能通过代码极短一眼就能看懂。如果你是在一个不追求性能的业务场景里临时校验括号这样写是最省事的。5.2 它的性能问题与隐藏的雷替换消除法最大的问题是性能。String.replace每次调用都会完整扫描一遍字符串并生成新的字符串对象。假设字符串有 n 层嵌套每轮至少消除一层最坏需要 O(n) 轮每轮 O(n) 扫描综合时间复杂度是 O(n^2)。如果嵌套特别深这个开销是实打实的。还有一个容易被忽略的坑replace方法底层要处理字符匹配和数组复制连续调用三次replace时上一轮刚生成的新字符串又会被下一轮replace全量扫描一遍。明明只消掉几个字符却把整串重新复制了好几次非常不划算。如果换成正则表达式replaceAll就更慢了正则匹配本身有额外的编译和执行开销而且还得小心翼翼地处理括号的转义字符完全没有必要。所以我的结论是方案四适合作为想证明自己思路开阔时的补充但绝对不要把它当成正式答案。面试官如果追问它的复杂度你最好能脱口而出 O(n^2)并且能说出因为它每轮只消除一层嵌套需要反复扫描这样的原因。这样哪怕你不推荐这个方案面试官也知道你不是不懂只是做了取舍。6. 方案五计数器法作为反例反而能讲清楚栈的必要性6.1 在单一类型括号下计数是可行的假设题目退化成最简单的情况字符串里只有(和)两种字符判断括号是否有有效。这时候完全不需要栈一个计数器就够了。public boolean isValid(String s) { int count 0; for (char ch : s.toCharArray()) { if (ch () { count; } else { count--; if (count 0) { return false; } } } return count 0; }逻辑非常直白遇到(加一遇到)减一任何时候计数器变成负数说明)多出来了直接失败遍历完计数器必须归零否则说明有(没有匹配。这个方案的时间复杂度是 O(n)空间复杂度是 O(1)在三种括号场景下是不可能做到的。但如果题目只涉及一种括号它就是最优解连栈都不需要。6.2 为什么([)]让计数器彻底失效一旦括号类型增加到三种计数器方案就崩了。问题不在于计数器能不能统计数量而在于它丢失了顺序和类型两个关键信息。看一个例子([)]。按计数器方案统计左括号数量是 2右括号数量也是 2最终数量和类型都能对上会误判为有效。但这个字符串实际上是无效的因为它不是一个合法的括号嵌套结构。用图示能看得很清楚(期待的是)但[插在两者之间[期待的是]但显然)出现时最内层还没有关闭。这种交叉嵌套在视觉上表现为括号线交叉在结构上是完全非法的。为什么栈能解决这个问题因为栈不仅保存了有哪些左括号还没匹配还保存了它们的出现顺序。当遇到一个右括号时栈顶就是当前最近、最应该被匹配的左括号。如果最内层的期待类型不匹配整个字符串就无效。计数器只有数量没有先后顺序自然无法判断这种情况。所以计数器法在三种括号的场景下更多是作为一个反例存在。面试时你可以主动提这么一句如果只有一种括号O(1) 空间的计数器就行但多类型时不行因为我们需要保留顺序信息所以栈是必要的。这句话会让面试官意识到你不仅知道怎么做还知道为什么要这样做以及不同方案之间的边界在哪里。7. 五种方案横向对比以及面试时到底该先讲哪个7.1 复杂度与代码量对比五种方案的取舍放到一张表里看最清楚方案平均时间复杂度空间复杂度代码量面试推荐度栈 哈希表O(n)O(n)短首选数组模拟栈O(n)O(n)稍长追问时展示递归消除法O(n^2)O(n) 递归栈短思路补充替换消除法O(n^2) 最坏O(n)最短不推荐计数器法O(n)O(1)最短仅限单一括号场景这里有一个经常被搞混的细节递归消除法和替换消除法都不能简单地说空间复杂度是 O(1)。递归消除法的递归调用会占用调用栈空间替换消除法则因为不断生成新的字符串每次替换都占用新内存。只有计数器法真正做到了 O(1) 空间。时间复杂度方面栈解法和数组模拟栈都是线性时间已经是最优解。递归消除法和替换消除法虽然在小数据量下跑得也很快但数据规模一大O(n^2) 的开销会明显暴露。7.2 一套稳妥的答题顺序聊了这么多方案最后给一个可以直接照抄的面试策略。核心原则是先稳后秀先用最常规的方案拿到分再用补充信息展示深度。我的建议是这样的节奏第一步结论先行。直接说这道题可以用栈来解决核心是左括号入栈、右括号弹栈并检查匹配。第二步讲边界。主动提到字符串长度为奇数、遍历到右括号时栈为空、遍历结束后栈不为空这三点。把边界讲清楚比机械地写代码更能体现你的严谨。第三步写方案一。代码短、可读性高、复杂度最优这是最稳妥的答案。第四步如果面试官追问能不能不用现成栈切到方案二顺便讲一句输入长度已知数组容量可以一次开满避免动态扩容。第五步如果面试官追问还有没有其他思路聊递归消除法或替换消除法但一定要主动补一句它们时间复杂度退化到 O(n^2)所以工程上不常用。第六步只有在下班后面试官想闲聊或者这是一道开放性问题时再聊计数器法。正常面试中计数器法更适合在讲完栈解法之后作为为什么用栈的反面论证来提一嘴而不是单独作为一个答案。五个方案全部往外倒是最容易翻车的面试官会觉得你没有重点抓不住主次。一次面试不需要展示所有解法只需要展示出你能在最合适的时机给出最合适的答案。8. 题目之外两道变体题与生产环境里的括号匹配8.1 变体题一最长有效括号LeetCode 第 32 题最长有效括号是在 #20 的基础上做文章不是判断整个字符串是否有效而是找出最长的有效括号子串的长度。这道题用栈也能做但技巧性更强。需要在栈底预先放一个-1作为哨兵用来标记最后一个未匹配右括号的位置。具体来说遇到(就入栈入栈的是当前索引遇到)就出栈如果出栈后栈为空说明当前右括号没有匹配的左括号把它作为新的哨兵压入栈如果出栈后栈不为空说明从栈顶索引的下一个位置到当前位置是一段有效子串用i - stack.peek()更新答案。这个思路和 #20 的栈解法一脉相承区别在于 #20 遇到栈空时直接判定无效而 #32 遇到栈空时把这当作一段有效区间的起点记录下来。一个细微的差别解决的问题就从是否有效变成了最长有效长度是多少。8.2 变体题二删除无效的括号LeetCode 第 301 题删除无效的括号要求删除最少数量的括号使得整个字符串变成有效的括号字符串。这道题一般用 BFS 或者回溯而判断某个候选字符串是否有效背后调用的正是今天这道题的判断逻辑。如果用 BFS 来做每一层枚举删除一个括号后的所有可能字符串然后用一个isValid来判断每个候选串是否有效第一个合法结果就是答案。isValid内部实现就是我们前面讲过的栈解法。那本题的某个方案会被当作其他题目里的一个子模块反复调用。这也是刷题的价值——很多题看起来是新的底层缝缝补补用的都是最常见的那几个原语。有效的括号就是原语之一。8.3 生产环境里的括号匹配抛开考试和刷题括号匹配在真实工程里的应用比我最初预想的要广得多。编译器方向各种语言的表达式解析都要检查括号是否配对、嵌套层级是否合法。一个简单的递归下降解析器核心逻辑就是不断匹配左括号和右括号。代码编辑器方向括号高亮和自动补全功能也需要在输入每个字符时判断当前括号栈的状态([{的亮色配对本质上就是一个栈的应用。HTML 和 XML 的标签校验也可以理解为括号匹配的变体只是标签名代替了(和)。表达式求值系统里中缀表达式转后缀表达式、计算器处理括号优先级背后同样是栈在支撑。可以说括号匹配是整个结构化文本处理的基础模块。所以这道题真正训练的其实是一种识别嵌套结构的能力。这种能力一旦建立你再去看递归下降、JSON 解析、模板引擎、Tag 配对这类问题都会有这题我见过的感觉。最后分享一个我刷题多年的个人习惯拿到一道题尽量逼自己写至少三种解法哪怕其中两种是不推荐的。因为第一种解法让你会做第二种解法让你看穿本质第三种解法让你知道边界。这道 #20 特别适合用来做这个训练因为它足够简单可以把所有注意力都放在为什么上而不是被复杂的业务逻辑绕晕。等你把五种方案都吃透了再去碰 #32、#301、#22 这些括号家族的其他成员会发现一路顺畅。
