LeetCode 32 最长有效括号：三种解法详解与边界陷阱

1. 题目拆解：Hard题里的"最长连续"到底在考什么

LeetCode 32 最长有效括号（Longest Valid Parentheses），我在刷题列表里见过它太多次了。题目本身一句话就能说完：给定一个只包含 '(' 和 ')' 的字符串，找出最长的有效且连续的括号子串长度。比如输入"(()"，答案是 2，因为中间那块"()"长度是 2，而整个字符串并不是合法的括号串；输入")()())"，答案是 4，因为中间有一段"()()"是连续的合法括号子串。题目还有个限制：空字符串的长度是 0。

我第一次做这题的时候，第一反应是"这不就是第 20 题有效的括号吗，用栈扫一遍不就完了"。但真正动手之后才发现完全不是一回事。第 20 题只要求判断整个字符串是不是合法的括号序列，遇到不匹配的字符直接返回 false 就结束了；这道题要求的是从一个可能存在多处断裂、多段合法片段的字符串里，找出最长的那一段。它不关心全局是否合法，只关心局部连续匹配的最大长度。用生活里的话说，第 20 题是"检查一篇作文有没有语法错误"，这一题是"在一篇满是病句的作文里，找最长的一句完整通顺的话"。

题目里最要命的是"连续"两个字。连续意味着你不能像求子序列那样跳过中间不合法的字符，一旦中间被一个孤立的括号隔断，前面的长度就得全部作废。比如"())()"，前面"()"是合法的，中间一个单独的右括号把整个区间切断了，后面"()"又从头开始算，所以最长只能是 2，不是把前后拼起来的 4。这一点很多人写暴力枚举的时候就会踩进去，因为只看左右括号数量相等还不够，还要保证任意前缀中左括号数量不小于右括号数量。换句话说，")("这种左右数量相等的子串，实际上根本不是一个合法括号子串。

这道题虽然标着 Hard，但核心考点非常集中：字符串线性扫描、栈的使用、动态规划的状态设计，以及如何用常数空间解决区间最值问题。常见的三种线性解法分别是动态规划、栈、左右双向扫描。我认为把这三条路都走一遍，比单纯背代码有价值得多，因为它们分别对应了"状态定义""数据结构选型""空间优化"三类不同的思考方式。

2. 动态规划解法：用dp[i]锁定"以i结尾"这个关键状态

2.1 状态定义为什么必须带"结尾"

先说结论：dp[i]表示以字符s[i]作为右端点时，能形成的最长有效括号子串的长度。这个"以 i 结尾"是整道题 DP 思路的命门。

为什么不定义成"从 0 到 i 的最长有效括号长度"？因为括号匹配这件事有强烈的方向性。一个有效括号子串一旦闭合，它右侧紧挨着的下一个字符能不能继续参与构成更长的子串，取决于它左侧紧贴的那段是否已经闭合完整。定义必须以某个位置为结尾，才能把"这一段已经闭合、长度为多少"的信息准确传给后面的字符。这其实和最大子数组和的 DP 思路同源：你想求全局最值，但状态必须落在局部端点，否则没办法递推。

如果s[i]本身是'('，那以它结尾的合法子串长度一定是 0，因为没有一个"合法括号子串"会以一个未闭合的左括号作为右端点。这个处理看起来简单，但实际上帮 DP 自动做了"断点隔离"：中间只要出现任何一个不匹配的位置，对应位置的 dp 就是 0，后续拼接自然就从 0 开始，不会跨过断点。

2.2 两类转移与下标边界陷阱

真正需要分析的是s[i] == ')'的情况。此时 i 前一个字符是谁，决定了两种完全不同的转移路径。

第一种情况，s[i-1] == '('。这两个字符直接配对，基础长度为 2，如果s[i-2]还能作为某个有效子串的右端点，前面的部分也要接上，所以dp[i] = dp[i-2] + 2（当 i-2 存在时，否则就只是 2）。举例来说，"()()"在 i=3 这个右括号的位置，dp[3] = dp[1] + 2 = 2 + 2 = 4，它把前一段"()"和后面新配对的"()"拼成了完整的一段。

第二种情况，s[i-1] == ')'，说明 i 左侧紧贴着一个已经闭合好的有效子串，这个子串的长度是dp[i-1]。想让s[i]这个右括号也能加入进来，就必须在它左侧找到对应的左括号。具体位置就是j = i - dp[i-1] - 1。如果j >= 0且s[j] == '('，那么s[j]和s[i]形成一对新括号，把中间那段已经有效的子串包在了里面。此时dp[i] = dp[i-1] + 2。但还没结束：s[j]左边可能还接着一段有效子串，也就是dp[j-1]，也需要接上，所以再补dp[i] += dp[j-1]（当 j-1 存在时）。

这里最容易翻车的点全在下标边界。写代码的时候，i - 2 >= 0、j >= 0、j - 1 >= 0三个条件少一个都有可能越界或者少算一段。很多题解里喜欢把dp[-1]当作 0 来处理，但 Python 里列表索引-1会直接取最后一个元素，这是个大坑，所以我习惯在代码里用条件判断把边界挡掉，宁可多写几个 if，也不依赖语言特性。

2.3 一步步运行"()(())"：从dp数组看匹配过程

直接看代码会更清楚：

class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) if n == 0: return 0 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 if j - 1 >= 0: dp[i] += dp[j - 1] ans = max(ans, dp[i]) return ans

拿"()(())"手动跑一遍。这个例子特别适合理解嵌套和并列两种结构同时出现时，DP 是怎么工作的。

i=1，s[1] 是')'，s[0] 是'('，直接配一对，dp[1] = 2。i=2 和 i=3 都是左括号，dp 都为 0。i=4，s[4] 是')'，s[3] 是'('，属于第一种情况，dp[4] = dp[2] + 2 = 2，此时"()"这一对闭合。i=5，s[5] 是')'，s[4] 是')'，走第二种情况。dp[4] = 2，所以j = 5 - 2 - 1 = 2，而s[2]正好是'('，于是dp[5] = dp[4] + 2 = 4。再看j - 1 = 1，dp[1] = 2，说明这个左括号前面还接着一段"()"，把两段一起拼上，最终dp[5] = 6。

整个过程能看到一个很漂亮的特性：DP 天然处理了"并列拼接"和"嵌套包裹"两种结构。dp[i-1]负责传递右侧已经闭合的长度，dp[j-1]负责传递左侧已经闭合的长度，中间通过一对新括号把它们连起来。这也是为什么我说这道题适合用来理解"状态设计要带端点"这个思路，比死记转移方程有意义得多。

3. 栈解法：哨兵元素-1为什么能一招定乾坤

3.1 栈内存下标而不是括号，本质是把"断点"留在栈里

很多人从第 20 题走过来，很自然地想在栈里存字符'('或')'。但这道题里栈里存的下标才是关键。为什么？因为最终要求的是长度，而长度必须由位置相减得到。你只存一个字符，根本不知道这一对括号在字符串里的具体位置，也就无法算出"从哪到哪"是有效的。

栈的语义其实很单纯：栈底到栈顶，存的是"到目前为止，那些还没被匹配掉的左括号的下标"，以及历史上曾经出现的、不能再继续参与匹配的"断点"下标。每当我们用一个右括号弹出栈顶左括号时，新的栈顶天然就是当前有效区间左侧边界的前一个位置。于是当前有效区间的长度就是当前下标 - 栈顶下标。这里的核心思想不是匹配本身，而是用栈维护"最后一个失效位置"，这个位置就是计算区间长度的锚点。

我可以打个比方：栈里的元素像一串打了结的绳子上的绳结。每遇到一个无法匹配的字符，就相当于绳子在这里打了个死结，后面无论绳子怎么绕，都不可能跨过这个结去和前面的部分组成完整的一段。栈顶的索引就是这个死结的位置。

3.2 代码实现与一条公式 i - stack[-1]

直接看代码：

class Solution: def longestValidParentheses(self, 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，它的意思是"整个字符串开始位置的前一位"。为什么需要这个哨兵？考虑最简单的情况"()"：i=0 遇到左括号，压入 0；i=1 遇到右括号，弹出 0。此时栈如果只有-1，那i - stack[-1] = 1 - (-1) = 2，正确算出长度 2。如果没有这个 -1，遇到第一个有效子串时栈会变成空，你还得特判"如果栈空就说明当前是一个完整串"，逻辑分支会多出一堆。

遇到右括号时，无论栈里是什么，先无条件pop()。这一步的目的是把"可能的匹配对象"或"哨兵"弹出去。如果弹出之后栈空了，说明这个右括号没能找到配对的左括号，它自己成为一个新的断点，所以要把当前下标i压回去，作为后续所有区间的新的起点基准。如果弹出之后栈还有元素，说明栈顶就是当前有效区间左边界的前一个位置，直接相减更新答案。

用")()())"走一遍：初始栈[-1]。i=0 是')'，pop 掉 -1，栈空，压入 0，此时栈[0]，意思是位置 0 是一个孤立右括号，后面任何合法区间都不可能越过它。i=1 是'('，压入 1，栈[0,1]。i=2 是')'，pop 掉 1，栈顶 0 还在，长度 = 2 - 0 = 2。i=3 压入 3，i=4 是')'，pop 3，栈顶还是 0，长度 = 4 - 0 = 4。i=5 是')'，pop 0，栈空，压入 5。最终答案 4。整个过程里，位置 0 的孤立右括号一直充当"断点基准"，一直没被替代，直到它自己被后续的右括号弹掉。

3.3 孤立右括号被pop后为什么要重新入场作哨兵

这是一个我当年想了很久的细节：为什么pop()之后如果栈空了，要把当前右括号下标i再压回去？这个右括号不是已经确定无法匹配了吗？压回去它以后还会被谁弹出来？

答案在于，它不需要再扮演"等待匹配的左括号"，它要扮演的是"断点"本身。假设字符串是")()"：i=0 的右括号把 -1 弹掉，栈空，如果我们不压 0 进去，那么 i=2 的右括号在 pop 掉 i=1 的左括号后，栈就空了，此时长度怎么算都算不对；但如果压了 0，i=2 时 pop 掉 1 后栈顶是 0，长度 = 2 - 0 = 2，正对应位置 1 和 2 组成的"()"。换句话说，孤立右括号把字符串切成了两半，它自己就是后半段的"起点前一位"，所有后续有效区间的长度都要从它后面开始算。

这个设计直接把"断点检测"和"长度计算"统一成了一条规则：栈里永远保证至少有一个元素，这个元素要么是未匹配的左括号下标，要么是断点下标。栈顶元素和当前右括号下标的差值，就是跨过断点之后、从断点右侧到现在为止能形成的最大有效长度。理解了这个之后，再看那行if not stack: stack.append(i)就不是死记硬背，而是"重新立一个断点坐标"。

4. 常数空间的左右双向扫描：O(1)内存破解Hard

4.1 为什么单向计数会漏解：以"(()"为例

栈解法的时间是 O(n)，空间也是 O(n)。如果面试官追问一句"能不能把空间压到 O(1)"，就需要拿出左右双向扫描这个解法。它的思路比 DP 和栈都更贴近括号匹配的计数本质。

先说一个反直觉的事实：很多有效括号子串，用简单的"左括号加一、右括号减一"从左到右扫一遍是找不出来的。看"(()"：从左往右数，位置 0 左括号计数 1，位置 1 左括号计数 2，位置 2 右括号，计数变成 1。整个过程计数始终大于 0，从来没有出现"左右数量相等"的瞬间，所以如果只在计数归零时更新答案，从左到右就什么都得不到。但答案明明是 2，也就是位置 1 和 2 组成的"()"。

问题出在计数器的起点。从左往右时，我们默认从位置 0 开始累积；可一旦前面多出来一个无法闭合的左括号，这个多余的左括号会把后续所有的平衡点都"顶高"，导致即使出现了合法片段，计数也碰不到零。这里的本质是：从左向右只能发现那些"左括号最终被右括号抵消干净"的子串，却漏掉了"开头被多余左括号占据、但后面依然有合法片段"的情况。

4.2 左右双向扫描的计数规则

双向扫描的核心思路是：既然从左往右会被多余的左括号干扰，那就再从右往左扫一遍。右边扫描时，多余的右括号会被视为需要重置的断点，而左括号过多时同样需要重置，逻辑完全镜像。

具体规则分两趟。第一趟从左往右，维护 left 和 right 两个计数器，遇到'('让 left 加一，遇到')'让 right 加一。当 left 等于 right 时，说明当前累计的这段左右数量相等，是一个候选合法区间，用2 * right更新答案。当 right 大于 left 时，说明右括号过多，从当前起点开始不可能再构成合法区间，把两个计数器清零重来。第二趟从右往左，规则镜像：同样遇到'('让 left 加一，遇到')'让 right 加一，平衡时更新答案，但当 left 大于 right 时清零重来。

代码相当短：

class Solution: def longestValidParentheses(self, 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 == '(': left += 1 else: right += 1 if left == right: ans = max(ans, 2 * left) elif left > right: left = right = 0 return ans

第二趟更新答案时用2 * left还是2 * right其实无所谓，因为进入平衡分支时两者相等。真正的考点在重置条件：第一趟是right > left重置，第二趟是left > right重置，方向正好相反。一旦想当然地把第二趟也写成right > left，一些用例就会给出错误答案。

4.3 第二遍遍历里的一个隐藏重置坑

这个坑我印象很深。拿"())()("来测试，这个字符串的最长有效括号长度是 2，因为只有两个单独的"()"片段。但从右往左扫的时候，如果第二趟的重置条件写反，很容易算出 6。为什么？因为这个字符串的左右括号总数都是 3，如果不做任何重置，两趟扫描甚至可能在某个时刻错误地认为整个字符串是平衡的。

正确的第二趟扫描过程是这样的：从右往左遇到第一个字符是'('，left 变成 1，right 是 0，此时left > right，触发重置，计数器清零。如果不触发这个重置，窗口就会把这个孤立左括号一直带着，后面再遇到几个括号把计数补平，就可能误以为存在一段很长的合法区间。这种错误在样例不多的测试里很难发现，因为常规样例往往左右括号配得比较整齐。

这告诉我们一个道理：双向扫描的本质不是"找平衡点"，而是"同时用两趟扫描分别覆盖不同方向上的非法前缀"。第一趟覆盖了右括号导致的前缀失效，第二趟覆盖了左括号导致的前缀失效。两趟合在一起，才能保证所有可能的有效区间都能被某个方向的扫描发现。所以第二趟的重置条件，不是照抄第一趟，而是要根据扫描方向镜像翻转。

5. 边界用例与坑位盘点：把三种解法放在同一个测试台

5.1 七个必测样例的手算对照

算法题最怕的不是主流程写错，而是边界和特殊输入把代码击穿。我建议正式提交前，至少把这几个用例全部过一遍，它们基本覆盖了这道题的所有隐蔽分支。

这里我特别想强调"()(())"这个用例。它外层看是"一段()加上一段(())"的并列结构，所以正确答案是 6。用 DP 做的时候，i=5 那个位置的右括号不仅要把内部的(())包进来，还要把左侧已经闭合的"()"也接上，如果你漏写了dp[j-1]的拼接，答案就会停在 4。这个用例能很好地检验状态转移是否写完整。

5.2 为什么这三种解法都能稳定O(n)，暴力为什么不行

题目给出的字符串长度上限通常是 3 万左右。如果上来就写暴力枚举，需要枚举所有子串，数量是 O(n^2)。就算用"同时维护左右括号计数"的优化，把判断合法子串压缩到 O(1)，9 亿次操作在大多数平台上依然会超时。而且暴力枚举还有一个隐蔽问题：只统计左右括号数量相等还不够，还要验证任意前缀左括号不少于右括号，这个验证在枚举时非常容易写漏。所以在这道题里，线性解法不是可选项，而是唯一能稳定落地的方案。

三种线性解法的时间和空间对比如下：

如果面试官问"能不能不用额外数组"，栈解法其实也符合"不用数组"的要求，因为栈是线性表，面试时聊到这里会被继续追问"能不能连栈都不用"，双向扫描就是收尾答案。我个人推荐把三种解法的复杂度背熟，现场推导顺序一般是：先答栈，再答双向扫描，最后按需补充 DP。

5.3 我在实际提交中踩到的下标越界与状态没清零

写 DP 解法时，我吃过两次亏。第一次是忘记了i - 2 >= 0的判断，导致"()"这种两个字符的输入直接访问dp[-1]，在 Python 里不会报错但会拿到最后一个元素，结果完全错误。第二次是在第二种转移里，判断j >= 0 and s[j] == '('之后，继续访问dp[j-1]时忘了检查j - 1 >= 0，结果在"()"这类简单用例上又翻车。下标问题在 DP 题里几乎不可避免，我的经验是：写完代码后，专门拿长度 0、1、2 的输入各跑一遍，再跑一个嵌套一个并列的复杂用例，基本能把越界和漏拼接都测出来。

写双向扫描时，我的问题则是另外一个类型：第二趟重置条件写反。第一趟是right > left重置，第二趟我习惯性复制过来，改成right > left，结果跑"())()("直接输出 6。排查了很久才发现第二趟应该用left > right。后来我养成一个习惯：每一趟的代码都单独注释上"当前重置条件代表哪个方向的非法前缀"，这样就算复制粘贴也不容易弄混。

6. 面试表达与刷题心得：从暴力到O(1)的临场节奏

6.1 第一反应：暴力枚举子串和为什么很快被否定

如果在面试现场拿到这题，先别急着写最优解，把暴力思路说清楚反而显得你思考路径完整。暴力做法是枚举左端点和右端点，对每个区间判断是否合法。判断方法很简单：维护一个计数器，遇到左括号加一，遇到右括号减一，如果中途计数器变成负数，说明右括号太多，区间非法；如果最终计数器等于零，说明合法。枚举所有区间需要 O(n^2)，判断合法性又需要 O(n)，总复杂度 O(n^3)。就算用增量法把合法性判断降到 O(1)，O(n^2) 依然不够看。

这个暴力思路的价值在于，它天然引出了两个关键观察：第一，合法的括号区间必然左右数量相等；第二，中间任何一个前缀如果右括号多了，这个区间就必须被切断。这两个观察分别对应了双向扫描和栈解法里的"重置"思想。所以哪怕暴力不能过题，也要能在面试里清晰讲出它为什么慢、慢在哪里。

6.2 面试官面前的推导路线：先栈，再O(1)，最后聊DP

我的建议是面试时按"栈 -> 双向扫描 -> DP"的顺序讲，而不是按题解常见顺序从 DP 开始。因为大多数人刚做过第 20 题有效括号，从栈入手最自然。先说出"如果栈里存下标，那么每次匹配成功，用当前下标减栈顶下标就是长度"，配合哨兵 -1 解释为什么第一个合法片段也能算出来，这已经是一版正确的 O(n) 解法。

接下来面试官大概率会问空间复杂度能不能再省。这时候引出双向扫描：从左往右只能对付右括号过多的断点，从右往左才能对付左括号过多的断点，两趟扫描结合，空间变成 O(1)。讲的时候，重点强调第二趟的重置条件是镜像的，不能照抄第一趟。这里如果能主动举例说明"(()"是第一趟漏掉、第二趟找回的，说服力会很强。

如果面试官还想考察状态设计，再讲 DP。先定义"以 i 结尾"的 dp 含义，再分s[i-1] == '('和s[i-1] == ')'两类讨论，最后用"()(())"演示并列拼接。这样三条路都覆盖到了，无论是算法能力还是沟通能力都能展示出来。

6.3 周赛与日常刷题的一些细节习惯

在 LeetCode 热门 100 题和周赛讨论区里，最长有效括号经常被当成"看起来简单、写起来全是坑"的代表。我刷这道题时养成了几个习惯，写在这里供大家参考。

第一，先用暴力代码当"裁判"。我本地会写一个非常朴素的暴力函数，生成几千组随机括号串，然后拿三种解法和暴力结果比对。这个做法能非常快地发现双向扫描重置条件写错这类隐蔽问题，比我手动构造样例快得多。第二，善用"答案必然是偶数"这条性质自查。最长有效括号子串的长度一定是个偶数，如果某个用例跑出来奇数，基本可以断定状态转移或者计数器更新有问题。第三，提交前把空串、单字符、全左括号、全右括号这四类极短输入先跑一遍，这类输入能把索引进界问题一次性暴露出来。

这道题我后来在多个刷题群和讨论区里反复看到有人发帖问："为什么我栈解法明明看起来没问题，答案却不对？"大部分时候都是因为没有理解断点下标的作用，或者把i - stack[-1]误写成了i - stack[-1] + 1。后者是另一个常见误区：哨兵 -1 代表的是区间起点之前的位置，所以不需要加一；只有当你存的是区间起始下标本身时才需要加一。理解了哨兵的语义，这一行公式就永远不会写错。

最后聊点我自己的习惯。我刷这题的时候是先写了暴力校验函数，再写三种解法，生成几千组随机括号串做暴力比对。随机测试跑了几轮之后，双向扫描第二遍的重置条件问题果然被揪出来了。这种"拿暴力当裁判"的刷题方式，比对着样例干想稳得多，也更有意思。如果时间充裕，我建议你也把三种解法都写一遍，再用随机数据互相验证；这道题值得这个投入。