最长有效括号：栈、动态规划与O(1)空间扫描全解析

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 本身就以有效子串开头时，比如 "()"，计算长度需要用到栈底的位置 -1：i=1 时弹出 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) { Deque<Integer> 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 两个经典用例的逐步模拟

先看 "(()"。这个用例专测"左括号盈余"的情况，很多解法在这里会算错。

答案 2，来自下标 1-2 之间的 "()"。注意这里如果栈里没有 -1 垫底，pop 之后栈空，逻辑会直接断掉，后面的长度计算全乱。再看标准范例 ")()())"，它前后都有多余的右括号，最能体现断点思想：

答案 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] + ...，遇到 "()" 这种短例子可能侥幸通过，但遇到 "()()" 就会在 i=3 时算出差之千里的结果。

用一个嵌套加拼接的综合例子验证："()(())"。dp 数组从 0 到 5 的推演如下：

最终答案 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 时更新答案。这个方法对 ")()())" 有效，但拿 "(()" 试一下就会发现：扫描到结尾时 left=2、right=1，左右始终不相等，答案一直是 0，可正确答案明明是 2。

问题出在"多余"的那个 '(' 在字符串末尾，正向扫描时它从来不触发清零条件，反而一直压着计数器，让内部那个 "()" 永远等不到 left==right 的时刻。换句话说，正向扫描能识别所有"右括号盈余"型的字符串，但遇到"左括号盈余"型就抓瞎了。

4.2 反向扫描的镜像规则

把字符串倒过来再扫一遍，问题就迎刃而解。反向扫描时，规则的左右镜像互换：遇到 ')' 给 right 加一，遇到 '(' 给 left 加一；当 left 超过 right 时清零重来，因为从右往左看，多出来的左括号才是"错误方向"的产物；left 等于 right 时更新答案。

"(()" 在反向扫描中是这样的：从右往左依次是 ')'、'('、'('。扫到 ')' 时 right=1，扫到第一个 '(' 时 left=1，两者相等，更新答案为 2。随后又扫到多余的 '('，触发 left>right 清零，但答案已经拿到了。

这个镜像思想很有意思：一个方向无法平衡的括号，颠倒视角后反而能正确配对。很多 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

现在解释为什么正反各扫一次就不会漏解。任意一个有效子串，如果正向扫描时错过了，说明它左边存在一些盈余的左括号一直压着计数，让它内部的 left==right 状态无法达成。但盈余左括号在反向扫描里恰好属于"错误方向"——反向规则会在遇到它们之前正常配对，因此这个子串在反向扫描里会被正确识别。反过来，如果正向扫描命中了，反向扫描最多是重复命中一次，取最大值不会出错。

这个方案的复杂度是 O(n) 时间、O(1) 空间，比栈和 DP 都省内存。代价是思维跳跃，面试时第一次听的人往往会愣一下，但一旦讲明白，就是全场最佳的"程序员的浪漫"。日常刷题时我也常拿它当最终优化手段，毕竟写惯了 O(n) 空间，能省下几个 MB 总是舒服的。

5. 三方案巅峰对决：面试选型与我的实战踩坑

5.1 横向对比：谁更快，谁更好写，谁最省空间

时间上三者平手，真正的分水岭在空间和思维门槛。栈解法最贴近人脑直觉，代码最短，出错率也最低，适合绝大多数面试场景；DP 解法展示了你对状态转移的掌控力，适合在讨论"线性 dp"时展开；双向扫描空间最省，是三分钟内的最优展示，但对方向感的考察非常严格，写反一个清零条件就全盘皆输。

5.2 面试现场的出牌顺序建议

我的实战习惯是三步走。

第一步，先给出 O(n²) 的计数扩展法确认题意，让面试官知道你没有卡壳，也给自己争取思考时间。第二步，立刻转栈解法，15 分钟内写出干净代码，这是保底分。第三步，如果面试官追问"能不能把空间压到 O(1)"，再上双向扫描。

不要把 DP 放在第一个讲。不是说 DP 不好，而是它的转移方程需要好几个用例才能让人信服，编码时间比栈长，一旦下标处理出错很难快速定位。栈解法在压力环境下更稳。如果面试官明确指定考"动态规划"，那顺序反过来：先给出 dp 定义和转移方程，再用用例验证，最后提一句"这道题还有栈和 O(1) 扫描两种思路"展示广度。两种出牌方式都覆盖了"解题能力 + 沟通能力"这两个面试核心考察点。

5.3 必须背下的边界用例清单

下面这组用例是我在本地写单元测试时固定挂上的，每写一个解法就让全部用例过一遍，比随机提交力扣有说服力得多。

特别是 "(()" 和 ")))(((" 这两种"盈余型"用例，三种解法里至少有两道会在这里翻车。我把它们放在自测用例的前排，任何一次重写代码都要先过这关，已经帮我拦下了不知道多少低级错误。

5.4 由第32题延伸出去的一串兄弟题

括号类问题在算法面试里是个大家族，掌握了这道题的三种视角，再刷下面这些题会轻松很多。

• 第20题《有效的括号》：基础配对，栈存字符即可，相当于本道题栈解法的简化版。
• 第22题《括号生成》：回溯生成所有合法括号组合，涉及卡特兰数直觉。
• 第678题《有效的括号字符串》：加入 '*' 通配符，双向扫描的计数思想直接派上用场。
• 第921题《使括号有效的最少添加》：单向计数即可，是双向扫描思路的降维应用。
• 第1541题《平衡括号字符串的最少插入次数》：同样是计数法扩展，对左右括号的处理要更细。

我个人刷题是"一拖五"策略：一道核心题讲透，立刻把相关题一次性做完。这套括号家族刷下来，对栈、线性 dp、贪心计数三种范式都会形成肌肉记忆，之后再遇到任何括号题，十分钟内就能定位到正确解法。

最后说一点个人体会。第32题最值钱的地方，不是让你背下三种解法，而是让你形成一种条件反射：看到"成对出现、可嵌套、可拼接"的结构，同时想到栈和以终点为状态的 dp 两条建模路径。我自己每次刷完一道解法，会把另外两种解法也各写一遍互相印证答案；一旦两个解法输出不一致，先别急着改代码，而是拿最短的用例从头手工模拟，一步一步对齐状态值。这道题里，我靠这个习惯抓到过至少两次下标越界，也靠它彻底搞懂了 dp[i] 转移二那行公式。希望这篇拆解也能给你同样的踏实感。