32. 最长有效括号
32. 最长有效括号
题目链接（困难）
题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
数据范围：
0 <= s.length <= 3 * 10^4s[i]为'('或')'
示例
示例 1：
输入： s = "(()"
输出： 2
解释： 最长有效括号子串是 "()"。
示例 2：
输入： s = ")()())"
输出： 4
解释： 最长有效括号子串是 "()()"。
示例 3：
输入： s = ""
输出： 0
核心思路
本题要求最长连续有效括号子串，和 LC 20（判断整体是否有效）不同，需要找最长的一段。
四种经典解法：
- 栈：用栈存未匹配的下标，栈底保存「最后一个未匹配的右括号下标」，用当前下标减栈顶得到长度；
- 动态规划：
dp[i]表示「以s[i]结尾的最长有效括号长度」，按s[i]和s[i-1]的情况分类转移； - 双指针（两次遍历）：正向扫一遍统计左右括号数，反向扫一遍处理多余的左括号，空间 $O(1)$；
- 暴力：枚举所有子串判断有效性，$O(n^3)$，不推荐。
推荐：栈（思路直观）或双指针（空间最优）。
方法一：栈
思路及解法
核心思想：用栈保存未匹配的左括号下标，并额外在栈底放一个「最后一个未匹配的右括号下标」作为边界。
流程：
- 初始化栈
stack = [-1]，-1作为边界，表示「当前位置之前没有有效的起点」； - 遍历字符串，对每个下标
i：- 若
s[i] == '('：把i入栈； - 若
s[i] == ')'：- 先弹出栈顶（尝试匹配一个左括号）；
- 若弹出后栈为空，说明这个
)没有匹配的左括号，它成为新的边界，把i入栈； - 若弹出后栈非空，说明匹配成功，此时
i - stack[-1]就是以i结尾的最长有效括号长度，更新答案。
- 若
为什么栈底保存边界：
- 栈底元素是「最后一个未匹配的位置」；
- 当前下标
i减去栈底元素，正好是「从栈底之后到i的合法区间长度」。
举例：s = ")()())"
i |
s[i] |
操作 | 栈 | 当前长度 | ans |
|---|---|---|---|---|---|
| 初始 | — | — | [-1] |
— | 0 |
| 0 | ')' |
弹出 -1，栈空，入栈 0 |
[0] |
— | 0 |
| 1 | '(' |
入栈 1 |
[0, 1] |
— | 0 |
| 2 | ')' |
弹出 1，栈非空，长度 2 - 0 = 2 |
[0] |
2 | 2 |
| 3 | '(' |
入栈 3 |
[0, 3] |
— | 2 |
| 4 | ')' |
弹出 3，栈非空，长度 4 - 0 = 4 |
[0] |
4 | 4 |
| 5 | ')' |
弹出 0，栈空，入栈 5 |
[5] |
— | 4 |
答案 4，正确。
代码
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复杂度分析
- 时间复杂度：$O(n)$，每个下标最多入栈、出栈一次。
- 空间复杂度：$O(n)$，栈最多存
n个下标。
方法二：动态规划
思路及解法
定义 dp[i] 表示「以 s[i] 结尾的最长有效括号长度」。
转移分类：
情况 1：s[i] == '('
- 以左括号结尾不可能构成有效括号，
dp[i] = 0。
情况 2：s[i] == ')'
- 若
s[i-1] == '('：s[i-1]和s[i]直接配对成"()"，长度为 2，加上s[i-2]结尾的有效长度：
- 若
s[i-1] == ')'：s[i-1]已经形成了一段有效括号，长度为dp[i-1]。要让它和s[i]配对，需要在dp[i-1]这段之前找一个左括号，位置是i - dp[i-1] - 1：- 若
s[i - dp[i-1] - 1] == '('，配对成功：
- 若
其中 dp[i - dp[i-1] - 2] 是配对左括号之前的有效长度。
边界：i - dp[i-1] - 1 >= 0 才可能配对；i - dp[i-1] - 2 >= 0 才加上前面的长度。
答案：max(dp)。
举例：s = "(()())"
i |
s[i] |
说明 | dp[i] |
|---|---|---|---|
| 0 | '(' |
左括号 | 0 |
| 1 | '(' |
左括号 | 0 |
| 2 | ')' |
s[1]='(' 配对 |
dp[0] + 2 = 2 |
| 3 | '(' |
左括号 | 0 |
| 4 | ')' |
s[3]='(' 配对 |
dp[2] + 2 = 4 |
| 5 | ')' |
s[4]=')'，往前找 i-dp[4]-1 = 0，s[0]='(' 配对 |
dp[4] + 2 + dp[-1] = 6 |
答案 6，正确。
代码
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
ans = 0
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
# 情况：s[i-1] 和 s[i] 直接配对
dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
# 情况：s[i-1] 结尾有一段有效括号，往前找左括号配对
dp[i] = dp[i - 1] + 2
if i - dp[i - 1] - 2 >= 0:
dp[i] += dp[i - dp[i - 1] - 2]
ans = max(ans, dp[i])
return ans复杂度分析
- 时间复杂度：$O(n)$，遍历一次。
- 空间复杂度：$O(n)$，
dp数组。
方法三：双指针（两次遍历，$O(1)$ 空间）✅ 推荐
思路及解法
核心思想：用两个计数器 left、right 分别统计当前区间内左、右括号的数量。
正向遍历：
- 遇到
'('：left += 1； - 遇到
')'：right += 1； - 当
left == right时，当前区间是有效的，更新ans = max(ans, 2 * right)； - 当
right > left时，说明右括号多了，不可能再和前面的左括号匹配，把left = right = 0重置。
问题：正向遍历只能处理「右括号多余」的情况，无法处理「左括号多余」的情况。
例如 s = "(()"，正向遍历：
left = 2, right = 1，从未出现left == right，答案0；- 但正确答案是
2（"()"）。
解决：反向遍历一遍，规则对称：
- 当
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复杂度分析
- 时间复杂度：$O(n)$，两次遍历。
- 空间复杂度：$O(1)$，只用两个计数器。
方法四：暴力法（不推荐）
思路及解法
枚举所有子串 s[i..j]，判断是否为有效括号串，取最长的。
代码
class Solution:
def longestValidParentheses(self, s: str) -> int:
def is_valid(sub: str) -> bool:
bal = 0
for ch in sub:
bal += 1 if ch == '(' else -1
if bal < 0:
return False
return bal == 0
n = len(s)
ans = 0
for i in range(n):
for j in range(i + 2, n + 1, 2): # 有效长度一定是偶数
if is_valid(s[i:j]):
ans = max(ans, j - i)
return ans复杂度分析
- 时间复杂度：$O(n^3)$，枚举 $O(n^2)$ 个子串，每个判断 $O(n)$。
- 空间复杂度：$O(n)$，切片开销。
不推荐，仅作思路参考。
四种方法对比
| 方法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 栈 | $O(n)$ | $O(n)$ | 思路直观，边界处理清晰 |
| 动态规划 | $O(n)$ | $O(n)$ | 状态定义严谨，转移稍复杂 |
| 双指针 | $O(n)$ | $O(1)$ | 空间最优，需两次遍历 |
| 暴力 | $O(n^3)$ | $O(n)$ | 不推荐，仅作对比 |
推荐：
- 面试开场：先讲栈，思路直观、易解释；
- 追问优化空间：讲双指针，展示 $O(1)$ 空间的技巧；
- 展示 DP 功底：讲动态规划，转移方程体现对结构的分情况分析。
关键细节
1. 栈底为什么放 -1
-1 是「虚拟的边界」，表示「当前位置之前没有有效的起点」。当栈弹出到空时，说明当前 ) 没有匹配，把它作为新的边界入栈。
长度计算：i - stack[-1] 而不是 i - stack[-1] + 1，因为 stack[-1] 是边界位置（不计入有效长度）。
2. 动态规划的两种情况
s[i-1] == '('：直接配对，dp[i] = dp[i-2] + 2；s[i-1] == ')'：s[i-1]结尾有一段有效括号，往前找i - dp[i-1] - 1处的左括号配对，配对后还要加上这段之前的有效长度dp[i - dp[i-1] - 2]。
易错点：边界判断 i - dp[i-1] - 1 >= 0 和 i - dp[i-1] - 2 >= 0 不能省。
3. 双指针为什么需要两次遍历
- 正向遍历只能处理「右括号多余」：一旦
right > left，后面不可能与前面匹配，重置； - 反向遍历处理「左括号多余」：一旦
left > right，重置。
例子：s = "(()"
- 正向：
left=2, right=1，left > right不重置，但也不更新答案，漏掉"()"； - 反向：
s[2]=')'→right=1；s[1]='('→left=1，left == right，答案2。
两次遍历互补。
4. 有效括号长度一定是偶数
如果 j - i 是奇数，一定不可能是有效括号串，暴力法可以跳过。
5. 为什么答案是 max(dp) 而不是 dp[n-1]
有效括号子串不一定以最后一个字符结尾。例如 s = "()(()"，dp 最后一位是 0，但答案在 dp[1] = 2。
总结
- 核心问题：找最长连续有效括号子串；
- 栈：
- 栈底放边界
-1； - 遇
)弹出，栈空则当前i成为新边界； - 栈非空时
i - stack[-1]为当前有效长度；
- 栈底放边界
- 动态规划：
dp[i]表示以i结尾的最长有效长度；- 分
s[i-1] == '('和s[i-1] == ')'两种情况；
- 双指针：
- 正向 + 反向各遍历一次；
- 正向处理右括号多余，反向处理左括号多余；
- 空间 $O(1)$；
- 通用套路：「最长有效括号」→ 栈 / DP / 双指针，三种都要会。
相关题目
- LC 20. 有效的括号（判断整体是否有效）
- LC 22. 括号生成（生成所有有效括号）
- LC 301. 删除无效的括号（DFS / BFS）
- LC 678. 有效的括号字符串（允许
*通配） - LC 921. 使括号有效的最少添加（贪心）
32. 最长有效括号
https://mingsm17518.github.io/2026/10/26/刷题笔记/Leetcode/32. 最长有效括号/