1. 先读懂题面有效括号子串到底在考什么1.1 题面解读与两个关键限制力扣热题100刷到第32期这天我发现一个特别巧的对应本期题号是32题目本身在力扣里的编号也是32——《最长有效括号》。这道题在Hard里属于那种一眼能读懂、暴力能写出来、但优雅解法要憋半天的典型也是动态规划和栈两派思路交锋最激烈的战场之一。题目要求很简单给定一个只包含 ( 和 ) 的字符串找出最长有效括号子串的长度。你看既没有复杂的数据结构定义也没有绕来绕去的边界约定可一旦动手设计O(n)解法立刻就会撞上两个流派的选择难题是用栈去模拟括号配对还是用动态规划去推导状态转移这篇文章我会把三种主流解法全部拆开讲清楚栈、动态规划、以及一个很多人不知道的O(1)空间双向扫描法。刷题主力适合进来对答案准备面试的朋友可以重点看第5节的选型策略和边界用例清单。老规矩不讲虚的直接上硬货。先抠字眼。子串二字决定了答案必须是连续的一段不能像子序列那样跳着选。比如 ()(() 这个串肉眼能看到两对独立的 ()但中间隔了一个孤立的 (最长有效子串长度就是 2而不是 4。所有括号类题目都容易在连续这个前提上想当然我最早刷这道题时也差点把子序列的思路带进来好在用例自测时及时发现。再来看有效的定义。一段括号子串有效需要同时满足三个条件左右括号数量相等任意前缀中右括号数量不超过左括号数量整体能够完整配对。前两条合在一起其实就是在说这串括号可以被完整消去中间没有任何刺头。这也是后面所有解法的共同出发点——你判断的永远不是一个孤立的括号而是一段可以闭环的区间。1.2 暴力法的天花板在哪里最直觉的思路是枚举所有子串再验证复杂度 O(n³)这种解法在面试里只能用来确认题意没有任何实用价值。稍微优化一下固定起点向右扩展用一个计数器 bal 维护左括号减右括号bal 为负立即中断当前起点bal 归零时更新答案。这样枚举所有起点复杂度降到 O(n²)。def longest_valid_bruteforce(s: str) - int: n, ans len(s), 0 for start in range(n): bal 0 for end in range(start, n): bal 1 if s[end] ( else -1 if bal 0: break if bal 0: ans max(ans, end - start 1) return ans我建议你拿到题目后先在纸上把这段代码写一遍再去想优化。为什么要这么做因为什么时候必须重置这个问题正是整道题的核心。暴力法里bal 一旦变成负数就必须中断重新开始而所有 O(n) 解法本质上都是在不同的数据结构里维护这个重置点——栈用下标记录它DP 用状态编码它双向扫描用计数器直接清零它。想通了这条线索三种解法就不再是三个孤立技巧而是同一件事的三副面孔。1.3 三个隐藏性质把 O(n) 的路铺好顺着暴力法的思路往下挖能总结出三条对解题至关重要的性质。第一有效子串不可能以 ( 结尾。结尾若多一个左括号整体左右数量必然失衡所以答案子串的最后一个字符一定是 )。反过来有效子串也不可能以一个多余的右括号开头否则前缀里右括号数量必然超标。第二括号配对满足就近匹配的嵌套结构。这种结构天然适合用栈来模拟就像我们手工消括号时总先消最里面那一对。同时每一段有效括号的长度可以作为状态向后传导这也给动态规划留了门。第三相邻的两段有效子串拼接起来仍是有效子串。()() 就是两个 () 拼出来的长度可以直接相加()(()) 更是拼接和嵌套同时发生。这条性质决定了 DP 里那些续接操作是合法的也决定了栈解法里栈顶到当前位置之间的区间可以放心计算长度。下面我按栈 → 动态规划 → 双向扫描的顺序逐个拆解。三种解法的时间复杂度都是 O(n)但空间、思维门槛和代码风格差别很大你可以在最后对照自己的习惯选型。2. 栈解法下标记账一次遍历找出所有有效段2.1 为什么栈里存的是下标不是字符很多人刷过第20题《有效的括号》习惯性在栈里塞 ( 或 ) 字符。那道题只问整个字符串是否有效字符够用但这道题问的是最长连续长度栈里必须存下标。原因很简单只有下标才能算出两个匹配括号之间的距离而这个距离就是有效子串的长度。更关键的是栈顶下标的语义不是当前括号而是最近一个没有被匹配掉的位置。从它到当前位置 i 之间的整段内容一定是连续且有效的括号组合因为中间只要出现过一个多余的括号它早就被弹出栈或者压入栈当作断点了。如果栈里只存字符这种位置信息完全丢失长度无从谈起。我自己就是从20题的惯性里带出来的受害者第一版代码栈里存括号字符跑完立刻意识到根本没法算长度白白浪费了十分钟。所以栈解法的第一原则存下标不存字符。下标既是配对凭证也是长度计算的刻度尺。2.2 哨兵 -1一个被很多人忽略的细节初始把 -1 压入栈它的作用有两层。第一它充当基准线。当 s 本身就以有效子串开头时比如 ()计算长度需要用到栈底的位置 -1i1 时弹出 0 后栈顶是 -1长度 1-(-1)2。如果栈初始为空这个长度是算不出来的你还得额外写分支去处理第一个字符就是左括号的情况代码立刻丑一倍。第二它统一了栈空的状态判断。遇到 ) 弹出后如果栈为空说明这个右括号没有匹配对象它就是新的一段有效子串开始之前的断点于是把它的下标压栈作为下一条基准线。有 -1 在底下垫着栈空这个分支的业务逻辑非常清晰不需要再区别对待。提示很多题解会把 -1 解释成虚拟的左括号前一位这个说法有点抽象。我更愿意把它理解成一个朴素的基准线——它就是整个字符串开始之前的位置任何从下标0开始的括号配对都要从这条线上量距离。2.3 代码实现与三个分支的推演def longest_valid_parentheses(s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans逻辑就三个分支。左括号无条件入栈相当于记下一笔待配对的账。遇到右括号先尝试从账本里销掉一个左括号如果账本空了说明当前右括号是多余的它本身变成新账本的起点如果账本还有货销掉之后栈顶就是最近未匹配位置用它当起点来计算最新有效段的长度。这里有一个极容易写错的分支顺序很多人把更新答案写在了栈空判断前面导致刚弹出的 -1 或者刚压入的断点被当成合法左边界算出的长度全是错的。比如输入 ()正确流程是先弹出0看到栈顶是 -1再算 1-(-1)2如果顺序写反栈 pop 后还没来得及判断就立刻取栈顶栈顶变成了0算出来的长度变成1答案当场挂掉。Java 版本顺手也给了面试时用惯哪个就用哪个。要点是必须用 Deque 模拟栈不要用 Stack 类。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; }2.4 两个经典用例的逐步模拟先看 (()。这个用例专测左括号盈余的情况很多解法在这里会算错。步骤字符操作栈内容答案0初始化压入 -1[-1]01(push 0[-1, 0]02(push 1[-1, 0, 1]03)pop 1栈顶 0[-1, 0]2答案 2来自下标 1-2 之间的 ()。注意这里如果栈里没有 -1 垫底pop 之后栈空逻辑会直接断掉后面的长度计算全乱。再看标准范例 )()())它前后都有多余的右括号最能体现断点思想步骤字符操作栈内容答案0初始化压入 -1[-1]01)pop -1栈空push 0[0]02(push 1[0, 1]03)pop 1栈顶 0[0]14(push 3[0, 3]15)pop 3栈顶 0[0]46)pop 0栈空push 5[5]4答案 4对应下标 1-4 的 ()()。下标 0 和 5 的两个多余右括号分别充当了两段有效区的断点。这就是栈解法的本质它把有效的连续段用一个个断点切分开来实时维护最大段长。整个过程只遍历一次字符串时间 O(n)空间最坏 O(n)。3. 动态规划解法dp[i] 的两种转移才是精髓3.1 状态定义为什么必须以 s[i] 结尾栈解法很直观但面试官一旦追问能不能用动态规划你就要拿出另一套完全不同的视角。动态规划这里常见的误区是定义 dp[i] 为前 i 个字符中的最长有效括号长度。这样定义做转移会很别扭因为有效子串必须在当前位置刚好结束才能向后拼接如果定义成全局最大值你根本不知道上一段有效子串在哪儿结束也就无法判断当前这个 ) 能不能接上去。所以标准做法是定义 dp[i] 为以 s[i] 结尾的最长有效括号子串长度。这个以谁结尾的视角是线性 dp 里非常核心的套路与其统计全局不如精确到每个位置的局部状态。它牺牲了一点直觉换来了转移方程的可计算性。由第1节的性质可知有效子串不可能以 ( 结尾所以但凡 s[i](dp[i] 直接等于 0只有 s[i]) 才需要认真推导。3.2 转移一配成 () 的直接拼接如果 s[i-1] (那 s[i-1] 和 s[i] 刚好配成最内层的 ()长度至少有 2。如果 i-2 位置还存在一段有效的子串这段子串与 () 相邻拼接后仍然有效所以dp[i] dp[i-2] 2类比一下这就像在一条已经铺好的铁轨上再接一段长度直接累加。边界是 i-2 0 时dp[i-2] 按 0 处理() 在最开头也是一种合法状态。这个转移最简单但它负责处理所有平铺直叙的拼接场景比如 ()() 的第二个括号。3.3 转移二外层嵌套与左边续接如果 s[i-1] )说明 s[i] 不能和 s[i-1] 直接配对它必须翻过一段已经形成的有效子串去匹配更早的一个 (。具体来说令 j i - dp[i-1] - 1这个 j 是以 s[i-1] 结尾的那段有效子串左边紧邻的位置。如果 j 0 且 s[j] (那么 s[j] 和 s[i] 配对成功把 dp[i-1] 那整段包在了中间外层的长度是 dp[i-1] 2再往前看j-1 位置若也有有效子串继续拼接于是dp[i] dp[i-1] 2 dp[j-1]当 j-1 0 时dp[j-1] 按 0 处理这个转移是整道 DP 解法的胜负手。它同时处理了两层含义内层已有的连续段被外层括号包裹后依然有效并且包裹之后还能和左边另一段有效子串手拉手连成长串。没有后面那个 dp[j-1]遇到 ()(()) 这种外层包着内层、左边还连着一截的结构就会漏算。3.4 完整代码与下标越界的三个坑def longest_valid_parentheses_dp(s: str) - int: n len(s) dp [0] * n ans 0 for i in range(1, n): if s[i] ): if s[i-1] (: dp[i] (dp[i-2] if i 2 else 0) 2 else: j i - dp[i-1] - 1 if j 0 and s[j] (: dp[i] dp[i-1] 2 (dp[j-1] if j 1 else 0) ans max(ans, dp[i]) return ans三个坑我在实际写的时候全部踩过一遍逐个说。第一i-2 可能越界。Python 里 dp[-1] 不会报错但会默默拿到数组最后一个元素结果全错。必须用 i 2 显式判断。我第一次写就是直接 dp[i-2] 2短用例全过一到 () 开头的长串就出诡异结果排查了半天才发现是负下标在捣鬼。第二j 可能为负。j 小于 0 说明 s[i] 左边连一段有效子串都不存在直接跳过不能访问 s[j]。Python 的 s[-1] 是合法语法但语义完全错误——它会取到字符串最后一个字符这种负下标陷阱最容易在做自测时漏掉因为短用例里 j 常常恰好不小于 0。第三dp[j-1] 的取值。j-1 等于 -1 时按 0 算否则取 dp[j-1]。这里一旦贪图省事直接写成 dp[j-1] ...遇到 () 这种短例子可能侥幸通过但遇到 ()() 就会在 i3 时算出差之千里的结果。用一个嵌套加拼接的综合例子验证()(())。dp 数组从 0 到 5 的推演如下i字符转移路径dp[i]0(左括号直接置001)s[0](dp[1]dp[-1]222(左括号直接置003(左括号直接置004)s[3](dp[4]dp[2]225)s[4])j5-2-12s[2](dp[5]dp[4]2dp[1]6最终答案 6整串有效。注意 dp[5] 那一行内层 dp[4]2 对应下标 3-4 的 ()s[2]( 与 s[5]) 在外部配对然后左边续上 dp[1]2 也就是下标 0-1 的 ()三段合体为 ()(())。这就是转移二把嵌套和拼接一并解决的威力少了 dp[j-1] 那一项正确答案会变成 4。4. 常数空间双向扫描打败所有辅助结构的野路子4.1 一次扫描为什么不够栈和 DP 的空间都是 O(n)于是很多人开始想能不能用一个计数器从左往右扫一遍就把答案算出来思路是这样的left 记录左括号数right 记录右括号数。right 超过 left 时清零重来left 等于 right 时更新答案。这个方法对 )()()) 有效但拿 (() 试一下就会发现扫描到结尾时 left2、right1左右始终不相等答案一直是 0可正确答案明明是 2。问题出在多余的那个 ( 在字符串末尾正向扫描时它从来不触发清零条件反而一直压着计数器让内部那个 () 永远等不到 leftright 的时刻。换句话说正向扫描能识别所有右括号盈余型的字符串但遇到左括号盈余型就抓瞎了。4.2 反向扫描的镜像规则把字符串倒过来再扫一遍问题就迎刃而解。反向扫描时规则的左右镜像互换遇到 ) 给 right 加一遇到 ( 给 left 加一当 left 超过 right 时清零重来因为从右往左看多出来的左括号才是错误方向的产物left 等于 right 时更新答案。(() 在反向扫描中是这样的从右往左依次是 )、(、(。扫到 ) 时 right1扫到第一个 ( 时 left1两者相等更新答案为 2。随后又扫到多余的 (触发 leftright 清零但答案已经拿到了。这个镜像思想很有意思一个方向无法平衡的括号颠倒视角后反而能正确配对。很多 O(1) 空间的题解都藏着类似的换方向看问题的哲学。4.3 代码实现与为什么双向不会漏def longest_valid_parentheses_scan(s: str) - int: ans 0 left right 0 for ch in s: if ch (: left 1 else: right 1 if left right: ans max(ans, 2 * right) elif right left: left right 0 left right 0 for ch in reversed(s): if ch ): right 1 else: left 1 if left right: ans max(ans, 2 * left) elif left right: left right 0 return ans现在解释为什么正反各扫一次就不会漏解。任意一个有效子串如果正向扫描时错过了说明它左边存在一些盈余的左括号一直压着计数让它内部的 leftright 状态无法达成。但盈余左括号在反向扫描里恰好属于错误方向——反向规则会在遇到它们之前正常配对因此这个子串在反向扫描里会被正确识别。反过来如果正向扫描命中了反向扫描最多是重复命中一次取最大值不会出错。这个方案的复杂度是 O(n) 时间、O(1) 空间比栈和 DP 都省内存。代价是思维跳跃面试时第一次听的人往往会愣一下但一旦讲明白就是全场最佳的程序员的浪漫。日常刷题时我也常拿它当最终优化手段毕竟写惯了 O(n) 空间能省下几个 MB 总是舒服的。5. 三方案巅峰对决面试选型与我的实战踩坑5.1 横向对比谁更快谁更好写谁最省空间解法时间复杂度空间复杂度核心思路实现难度典型失误栈O(n)O(n)用下标账本记录断点与配对较低栈里存字符、忘记 -1 哨兵动态规划O(n)O(n)以 s[i] 结尾的状态转移中等负下标越界、转移条件漏判双向扫描O(n)O(1)双向计数配对盈余括号自动出局中等反向清零条件写反时间上三者平手真正的分水岭在空间和思维门槛。栈解法最贴近人脑直觉代码最短出错率也最低适合绝大多数面试场景DP 解法展示了你对状态转移的掌控力适合在讨论线性 dp时展开双向扫描空间最省是三分钟内的最优展示但对方向感的考察非常严格写反一个清零条件就全盘皆输。5.2 面试现场的出牌顺序建议我的实战习惯是三步走。第一步先给出 O(n²) 的计数扩展法确认题意让面试官知道你没有卡壳也给自己争取思考时间。第二步立刻转栈解法15 分钟内写出干净代码这是保底分。第三步如果面试官追问能不能把空间压到 O(1)再上双向扫描。不要把 DP 放在第一个讲。不是说 DP 不好而是它的转移方程需要好几个用例才能让人信服编码时间比栈长一旦下标处理出错很难快速定位。栈解法在压力环境下更稳。如果面试官明确指定考动态规划那顺序反过来先给出 dp 定义和转移方程再用用例验证最后提一句这道题还有栈和 O(1) 扫描两种思路展示广度。两种出牌方式都覆盖了解题能力 沟通能力这两个面试核心考察点。5.3 必须背下的边界用例清单下面这组用例是我在本地写单元测试时固定挂上的每写一个解法就让全部用例过一遍比随机提交力扣有说服力得多。输入期望输出考察点0空串(0单左括号)0单右括号()2最小有效段(()2左括号盈余专测反向扫描)()())4标准示例前后杂质((()))6纯嵌套()(())6拼接 嵌套混合(()())6多段拼接)))(((0左右分离全部无效特别是 (() 和 )))((( 这两种盈余型用例三种解法里至少有两道会在这里翻车。我把它们放在自测用例的前排任何一次重写代码都要先过这关已经帮我拦下了不知道多少低级错误。5.4 由第32题延伸出去的一串兄弟题括号类问题在算法面试里是个大家族掌握了这道题的三种视角再刷下面这些题会轻松很多。第20题《有效的括号》基础配对栈存字符即可相当于本道题栈解法的简化版。第22题《括号生成》回溯生成所有合法括号组合涉及卡特兰数直觉。第678题《有效的括号字符串》加入 * 通配符双向扫描的计数思想直接派上用场。第921题《使括号有效的最少添加》单向计数即可是双向扫描思路的降维应用。第1541题《平衡括号字符串的最少插入次数》同样是计数法扩展对左右括号的处理要更细。我个人刷题是一拖五策略一道核心题讲透立刻把相关题一次性做完。这套括号家族刷下来对栈、线性 dp、贪心计数三种范式都会形成肌肉记忆之后再遇到任何括号题十分钟内就能定位到正确解法。最后说一点个人体会。第32题最值钱的地方不是让你背下三种解法而是让你形成一种条件反射看到成对出现、可嵌套、可拼接的结构同时想到栈和以终点为状态的 dp 两条建模路径。我自己每次刷完一道解法会把另外两种解法也各写一遍互相印证答案一旦两个解法输出不一致先别急着改代码而是拿最短的用例从头手工模拟一步一步对齐状态值。这道题里我靠这个习惯抓到过至少两次下标越界也靠它彻底搞懂了 dp[i] 转移二那行公式。希望这篇拆解也能给你同样的踏实感。