LeetCode 热题 100 里的括号题有不少但“最长有效括号”绝对是最容易让人产生“我写完了”错觉的一道。我第一次刷这道题时两分钟就写出了一个栈解法自信满满点了提交结果直接被一个测试用例打脸——当时我就意识到这题考的根本不是你会不会用栈而是你对“连续”这两个字有没有真正敬畏。Java 版 LeetCode 刷题圈的共识是热题 100 中这道题处在“动态规划/栈/计数”三种思路的交叉点上面试出现频率极高。无论你准备面试还是单纯想提升算法思维把这道题的三种解法彻底吃透性价比都非常高。本文我会用最长有效括号这道题作为主线完整拆解暴力法、栈解法、动态规划、双计数器法四种方案并且把每种方案背后的推导逻辑、容易踩的坑、以及面试官会怎么追问都交代清楚。1. 这题难在哪括号匹配不光是成对更重要的是“连续”先明确一下题目。“最长有效括号”说的是给定一个只包含(和)的字符串找出最长的有效well-formed括号子串的长度。比如(()答案是 2因为中间那段()是有效子串)()())答案是 4因为()()是最长的一段(()())答案是 6整个串都有效。看起来简单但很多人在第一步就栽了他们以为这题只要求“统计最多能匹配多少对括号”。如果只是统计配对数那()(()这个例子就很能说明问题——它最多能配出 2 对括号但最长的有效括号子串长度只有 2。因为有效的括号子串必须是连续的()后面跟着的(()把连续区间切断了你不能把前面的()和后面的()拼在一起算 4。为什么“连续”这么难处理因为括号串的合法结构有两种基本形态本质完全不同并列结构()()()是一段一段平铺开来的每一段之间可以无缝衔接。嵌套结构((()))是层层包裹的内层被外层完全覆盖。真实输入往往是两者的混合体比如()(())()既有并列又有嵌套。如果只用某个单一规则去判断很容易顾此失彼。所以这道题的第一道坎是理解“有效括号子串”的判定标准其实非常严格它要求从某个位置开始到某个位置结束这一整段内部的括号必须完全闭合且闭合过程从不出现右括号多于左括号的情况。为了把这条标准吃透我强烈建议你先把暴力解法写一遍。它的思路很直接枚举所有起点i然后从i往后扫描维护一个平衡值balance——遇到(就加 1遇到)就减 1。如果balance变成负数说明当前这段已经不可能合法了直接 break如果balance恰好等于 0说明从i到当前位置这一段是合法子串更新答案。public int longestValidParentheses(String s) { int n s.length(), ans 0; for (int i 0; i n; i) { int balance 0; for (int j i; j n; j) { balance s.charAt(j) ( ? 1 : -1; if (balance 0) break; if (balance 0) ans Math.max(ans, j - i 1); } } return ans; }这段代码的时间复杂度是 O(n²)空间复杂度 O(1)在 LeetCode 上会超时但它的价值在于把“有效括号子串”的定义翻译成了可执行逻辑balance 回到 0代表并列段闭合balance 从未跌穿 0代表嵌套结构合法。你会发现暴力法虽然慢但它天然正确因为它穷举了所有可能的连续区间。我见过不少刷题新手直接跳过了暴力法去背最优解结果面试时被问到“你是怎么想到这个解法的”就卡住了。实际上从暴力解到最优解的演化过程才是面试官真正想听的。暴力解是“基准答案”你只有先理解它后面讲栈解法和 DP 解法时才有坐标参照。2. 栈解法大多数人写错的第一版问题出在“哨兵”处理上栈是处理括号匹配最自然的工具所以绝大多数人的第一反应就是用栈。但这里有一个非常隐蔽的坑如果你只是像传统括号匹配那样遇到右括号就弹栈然后拿当前下标减栈顶下标来更新答案你会在某些用例上得到错误结果。先看一个典型的错误版本// 错误示范 public int longestValidParentheses(String s) { DequeInteger stack new ArrayDeque(); int ans 0; for (int i 0; i s.length(); i) { if (s.charAt(i) () { stack.push(i); } else { if (!stack.isEmpty()) { stack.pop(); ans Math.max(ans, i - stack.peek()); // 栈为空时会抛异常 } } } return ans; }这个写法至少有两个问题。第一当stack.pop()之后栈空了stack.peek()会直接抛EmptyStackException。第二就算你加了防空判断在()这种最简单的例子中第一个右括号弹掉左括号后栈为空你会因为取不到栈顶元素而无法计算长度。所以你需要一个非常关键的操作在栈中预先放入一个哨兵下标 -1。哨兵的作用是什么你可以把-1理解为“最后一个无法匹配的位置”。当栈里只剩下哨兵时说明从哨兵位置到当前右括号的这一整段都是合法子串所以i - (-1) i 1也就是从开头到当前位置的长度。而如果某个右括号发现栈已经空荡荡——连哨兵都被弹掉了——说明这个右括号没有匹配对象它就是新的“最后一个无法匹配的位置”把它压入栈中作为新的哨兵。正确写法如下public int longestValidParentheses(String s) { DequeInteger stack new ArrayDeque(); stack.push(-1); int ans 0; for (int i 0; i s.length(); i) { if (s.charAt(i) () { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) { stack.push(i); } else { ans Math.max(ans, i - stack.peek()); } } } return ans; }我建议你手动推演一个混合嵌套的用例比如()((())。流程拆解初始栈[-1]i0是(入栈栈[-1, 0]i1是)弹栈栈[-1]非空更新ans 1 - (-1) 2i2是(入栈栈[-1, 2]i3是(入栈栈[-1, 2, 3]i4是(入栈栈[-1, 2, 3, 4]i5是)弹栈栈[-1, 2, 3]非空ans max(2, 5-3) 2i6是)弹栈栈[-1, 2]非空ans max(2, 6-2) 4最终答案是 4对应子串(())或()((其实是下标 2 到 6 前面那一段((让我们重新看一下字符串()((())的实际结构字符依次是(、)、(、(、(、)、)。下标 2 到 6 是((())但它是有效的吗从左往右看(、(、(、)、)平衡值变化为 1、2、3、2、1最后没有归零所以它不是完整有效子串。真正有效的子串是下标 3 到 6 的(())长度 4以及下标 0 到 1 的()长度 2。答案 4 正确。这个例子的意义在于栈解法计算长度时用的不是“匹配了多少对”而是“当前右括号下标减去栈顶残留下标”。栈顶残留的永远是最后一个未匹配的位置所以这段长度天然是连续的。时间复杂度 O(n)每个字符最多入栈出栈一次空间复杂度 O(n)。栈解法唯一的缺点大概是需要你想明白哨兵的含义否则很容易写出边界条件错误的分支判断。另外说一句用Deque而不是Stack是我在 Java 开发中的习惯Stack继承自Vector有历史遗留的同步开销性能上不如ArrayDeque面试时可以顺嘴提一句算是加分项。3. 动态规划解法把“连续”翻译成状态转移而不是背方程如果说栈解法是“用结构匹配结构”那么动态规划就是“用状态记录结构”。我第一次接触这题的 DP 解法时也觉得方程很绕但后来想通了dp[i] 表示以第 i 个字符结尾的最长有效括号子串长度。注意这个定义——是以“第 i 个字符结尾”而不是“前 i 个字符”里包含的最长长度。这个区别是理解整个 DP 的关键。为什么必须以结尾字符为状态因为有括号串的有效性体现在最后一个字符上只可能以右括号)结尾。而以某个位置结尾的有效子串天然地强制了连续性——它不能跳过中间任何字符。确定 DP 状态后我们按s.charAt(i)分类讨论。第一类s[i]是(那它不可能作为有效子串的结尾所以dp[i] 0。第二类s[i]是)这时候要看向左边如果s[i-1]是(那它们俩直接配成一对dp[i] dp[i-2] 2。因为s[i-1]和s[i]这一对括号形成长度为 2 的核心前面如果还有以i-2结尾的有效子串就可以无缝拼接。比如()()当i3时s[2](dp[3] dp[1] 2 2 2 4。如果s[i-1]也是)说明s[i]想跟更前面的某个左括号配对。具体来说需要跳过s[i-1]所在的那一段有效子串去看i - dp[i-1] - 1这个位置。如果这个位置的字符是(那它就能跟s[i]配对。此时dp[i] dp[i-1] 2但这还没完——这个左括号的前面如果还接着一段有效子串也要拼上来所以还要加上dp[i - dp[i-1] - 2]。第二类第二种情况是最容易绕晕的地方我当年也是在这个分支上反复看题解才明白。用一个具体例子讲()(())我们盯住最后一个字符i5它是)s[4](所以第二种分支dp[4]是下标 4 这个字符结尾的最长有效长度等等下标 4 是(所以dp[4]0这个例子不适用于第二种分支。换一个例子(()())i5是最后一个)dp[4]表示下标 4 这个)结尾的子串长度s[1..4] ()()不对拆开看(()())中下标 1 是(、下标 2 是)、下标 3 是(、下标 4 是)。dp[4]就是以s[4])结尾的最长长度等于 4()()的一部分其实是下标 1 到 4 是()()对。现在s[5])想找左括号配对它应该跳过dp[4]4这一段去看i - dp[i-1] - 1 5 - 4 - 1 0下标 0 是(配对成功。于是核心部分是s[0]和s[5]包裹着s[1..4]这整段长度dp[4] 2 6。下标 0 前面没有字符了所以不额外加前缀长度最终dp[5]6整个串有效。关键点就在最后那句“前面如果还接着一段有效子串也要拼上来”——比如()(())这种形态的外层左括号前面还带着一段()当配好了最外层的(和)之后还要把左边那段()接上去。很多错误代码漏加的正是这一项。完整的 Java 实现如下public int longestValidParentheses(String s) { int n s.length(), ans 0; int[] dp new int[n]; for (int i 1; i n; i) { if (s.charAt(i) )) { if (s.charAt(i - 1) () { dp[i] (i 2 ? dp[i - 2] : 0) 2; } else { int prevLen dp[i - 1]; if (i - prevLen - 1 0 s.charAt(i - prevLen - 1) () { dp[i] prevLen 2; if (i - prevLen - 2 0) { dp[i] dp[i - prevLen - 2]; } } } ans Math.max(ans, dp[i]); } } return ans; }代码里有两处三元表达式处理数组越界这是 DP 的常规操作面试时也值得说明一下当i-2小于 0 时直接当作 0 处理。这版的空间复杂度是 O(n)因为需要一个长度和字符串一样的 dp 数组。理论上可以用滚动变量优化掉 dp 数组的中间依赖吗仔细看会发现dp[i]会用到dp[i-1]和dp[i-dp[i-1]-2]后面这个下标跳得比较远滚动变量不好做这也是 DP 解法在空间上不如双计数器法的原因。动态规划解法的价值不仅在于这题本身。它的思想可以推广到很多“求连续子串/子数组最优值”的问题比如最长递增子序列、最大子段和。核心方法论是找到一种定义让“以当前位置结尾的最优值”能够由更短位置的“结尾最优值”递推出来。这个“结尾”二字就是连续性的数学表达。4. 双计数器解法单次扫描注定有盲区反向再扫一遍才是完整答案如果面试官在你写完 DP 之后追问“能不能把空间优化到 O(1)”那他的目标就是这题的第三种经典解法——双计数器法也叫“两次扫描法”。它的思路精妙得有点反直觉只维护两个计数器 left 和 right分别记录遇到的左括号和右括号数量从左往右扫一遍再从右往左扫一遍答案就出来了。先看从左往右的第一遍。遇到(就left遇到)就right当left right时说明这一段左右括号平衡长度就是left * 2或者right * 2更新答案当right left时说明右括号成了“障碍”从当前位置往后不可能再和之前的部分构成合法子串了直接把两个计数器清零重新开始计数。这个逻辑看起来完美但有一个致命的盲区只从左往右扫遇到左括号特别多的情况会漏答案。比如(()从左往右扫left1,right0left2,right0left2,right1最后left ! rightans 始终没有被更新但正确答案是 2。原因很简单字符串末尾多了一个左括号导致计数器的平衡永远回不到 0但它中间明明有一段()是有效的。怎么补救从右往左再扫一遍镜像地处理这次遇到)就right遇到(就left。当left right时更新答案当left right时——注意这次是 left 大于 right 时清零——把计数器归零。为什么是 left 大于 right因为从右往左看字符串中的左括号变成了“未来方向上无法配对的多余字符”它会把本可以闭合的区间卡住。用(()验证从右往左i2是)right1,left0i1是(left1,right1相等更新ans2i0是(left2,right1left right清零。最终 ans2正确。完整代码public int longestValidParentheses(String s) { int ans 0, left 0, right 0; for (int i 0; i s.length(); i) { if (s.charAt(i) () left; else right; if (left right) ans Math.max(ans, left * 2); else if (right left) { left 0; right 0; } } left 0; right 0; for (int i s.length() - 1; i 0; i--) { if (s.charAt(i) () left; else right; if (left right) ans Math.max(ans, left * 2); else if (left right) { left 0; right 0; } } return ans; }为什么这个方案是对的本质上一个合法的括号子串在某个方向上扫描时必然会经历一次“左右计数器从 0 开始、最终归 0”的过程。从左往右扫能把右括号过多导致的子串失效处理掉从右往左扫能把左括号过多导致的子串失效处理掉两者取最大值就覆盖了所有合法子串的区间。这个思路最漂亮的地方在于它把空间从 O(n) 干到了 O(1)。我给读者的建议是双计数器法不要上来就背代码先用两个例子亲自推一遍(()和())。())从左往右扫left1,right0left1,right1更新 ans2left1,right2时 right left 清零。从右往左扫right1,left0right1,left1更新 ans2right1,left2时 left right不对这时候 left2哦这里要细心从右往左i2是)right1i1是)right2i0是(left1。整个过程左计数器最多 1右计数器 2最后 left1,right2left 没有大于 right所以第二次扫描不会更新错误答案。最终 ans2正确。这类“两趟扫描互补盲区”的思想很有迁移价值前缀和、区间覆盖、括号匹配变种题里都经常出现。你甚至可以把第二遍扫描理解为第一遍扫描的“对偶问题”一个方向解决一类边界条件组合起来覆盖全集。5. 三种方案横向对比与面试官追问的应对套路到这儿最长有效括号的经典解法已经全部过了一遍。面试和刷题中真正拉开差距的是你能不能快速说清三种方案的取舍、以及面对追问能不能稳住。我把核心对比整理成一张表解法时间复杂度空间复杂度扫描顺序核心难点暴力法O(n²)O(1)正向每个起点枚举仅作为 baseline理解题意栈解法O(n)O(n)正向单遍哨兵 -1 的维护动态规划O(n)O(n)正向单遍第二分支的前缀拼接双计数器O(n)O(1)正向 反向理解两个方向互补盲区面试时我会建议按这样的思路来讲先承认这道题最朴素的想法是 O(n²) 枚举然后说明括号匹配的自然数据结构是栈用栈可以做到 O(n)。如果面试官继续追问空间能不能更小再抛出双计数器法并解释为什么要扫两遍。这样整个思考路径是递进式的有逻辑层次。而 DP 解法可以作为“你还会不会其他思路”的补充题展示你对状态定义的敏感度——毕竟面试官不一定每题都只问最优解他也想看看你分析问题时的状态建模能力。面试官比较喜欢追问的变体题我总结几个如果现在要你输出最长有效括号子串本身而不是长度怎么做栈解法最方便在更新ans时同时记录start stack.peek() 1和end i最后用substring(start, end 1)取出来。DP 也可以用但要额外记录最优值对应的下标稍微麻烦一点。如果输入流是无限长的只能读一遍呢双计数器法直接出局因为它需要两遍扫描栈解法仍然适用但你要明白哨兵栈里存的永远是“未闭合的左括号下标”。这种场景更像真实的生产环境——流式处理中你不能把数据倒回去所以一遍扫描能出结果的数据结构更实用。如果括号种类从一种变成三种比如()[]{}这题怎么做那栈解法依然是主力但计数器法就不适用了因为不同括号是不能互相抵消的。这时候你甚至可以顺势聊到“有效括号字符串的匹配可以用有限状态自动机建模”之类的话题一般面试官喜欢听这种延伸。为什么双计数器法能保证覆盖所有答案这个问题经常被问到。我建议的回答是任何有效子串都对应一个左右括号数相等的区间在正向扫描中能检测到“右括号主导”的边界在反向扫描中能检测到“左括号主导”的边界两类边界覆盖了所有可能切割位置。只要边界处理完整答案就不会漏。还有一个小细节想提醒大家LeetCode 的输入可能包含大量字符用String.charAt()是最高效的访问方式不要图方便用s.toCharArray()之后再去遍历——虽然 charArray 访问也很快但在热题 100 这题的输入规模下两者没区别但面试写代码时保持对字符串的直接操作能让你避免不必要的内存拷贝讨论。从我个人的刷题体会来说这道题值得隔一段时间重新做一次。第一次你可能只会栈解法第二次能写出 DP第三次才真正理解双计数器为什么能扫两遍。每次重做都能发现新的理解层次这也是算法训练里少有的“一道题喂饱三种方法”的典型题。如果你正在准备 Java 面试能把这道题的来龙去脉讲到这个深度在候选人里已经算很能打的了。