32. 最长有效括号 (Hard)

专题归类： 10-动态规划 · 07-栈 LeetCode 链接： https://leetcode.cn/problems/longest-valid-parentheses/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 10

---

题目详细分析

• 数据范围：最长 3*10^4，O(n) 解法可行。
• 核心约束：子串必须连续（与子序列不同）且括号格式正确。
• 边界条件：空字符串返回 0；字符串全为 ( 或全为 ) 返回 0。
• 隐藏条件：简单的栈模拟可以判断括号是否匹配，但要求最长连续有效长度需要特殊处理。dp[i] 表示以 i 结尾的最长有效括号长度，只对 ) 有意义（以 ( 结尾的一定是 0）。

---

小白版直白理解

找出一段连续的括号串中，最长的一段”完美匹配”的括号。就像玩消消乐——遇到一对 () 就可以消掉，消完之后剩下的括号位置能告诉我们哪些是配对的。但我们要找的是最长的连续”能完全消掉”的那一段。比如 )()()) 中，最长的能消掉的是中间四个字符 ()()。

---

解题思路

思路一：动态规划（推荐）

核心洞察：dp[i] 表示以 s[i] 结尾的最长有效括号长度。只有 s[i] = ) 才可能非零。分两种情况：

1. s[i-1] = '('：配对，dp[i] = dp[i-2] + 2
2. s[i-1] = ')'：检查是否形如 (...(XXX))，需要找到与 s[i] 配对的位置

DP 五步法：

1. dp 定义：dp[i] 表示以 s[i] 结尾的最长有效括号子串长度
2. 递推公式：
   • s[i] = ’(’ → dp[i] = 0
   • s[i] = ’)’ 且 s[i-1] = ’(’ → dp[i] = dp[i-2] + 2
   • s[i] = ’)’ 且 s[i-1] = ’)’ → 找到配对位置 j = i - dp[i-1] - 1，若 s[j] = ’(’ → dp[i] = dp[i-1] + 2 + dp[j-1]
3. 初始化：全 0
4. 遍历顺序：从左到右，从 i=1 开始
5. 举例验证：s=”)()())” → dp[0]=0, dp[1]=0, dp[2]=2, dp[3]=0, dp[4]=2+2=4, dp[5]=0, max=4 ✓

def longestValidParentheses(s):
    n = len(s)
    if n < 2:
        return 0
    dp = [0] * n
    ans = 0
 
    for i in range(1, n):
        if s[i] == ')':                           # 只有 ) 可能配对
            if s[i - 1] == '(':                   # 情况 1: ...()
                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
            else:                                 # 情况 2: ...))
                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

思路二：栈

用栈存储下标，遇到 ( 入栈，遇到 ) 出栈，用当前下标 - 栈顶下标计算长度。

def longestValidParentheses(s):
    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(1)）

从左到右扫描，用 left 和 right 计数：当 left == right 时记录长度，当 right > left 时重置。再从右到左扫描一次防止漏掉 left > right 的情况。

def longestValidParentheses(s):
    left = right = ans = 0
 
    # 从左到右扫描
    for ch in s:
        if ch == '(':
            left += 1
        else:
            right += 1
        if left == right:
            ans = max(ans, left + 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, left + right)
        elif left > right:
            left = right = 0
 
    return ans

---

易错点

• dp 仅对 ) 有意义：以 ( 结尾的子串不可能是有效括号，dp 值为 0。
• 情况 2 的配对位置计算：j = i - dp[i-1] - 1 是核心难点，画图辅助理解。
• 拼接之前有效长度：最后要加 dp[j-1]，因为 XXX(...(XXX)) 前面可能还有有效括号。
• 双向扫描：如果只用单向扫描，((()) 这种情况会漏掉。
• 栈底初始为 -1：这是技巧，保证第一个 ) 也能正确计算长度。

---

框架提炼

括号匹配 DP 模板：

def parentheses_dp(s):
    n = len(s)
    dp = [0] * n
    ans = 0
    for i in range(1, n):
        if s[i] == ')' and i - dp[i-1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(':
            dp[i] = dp[i-1] + 2 + (dp[i - dp[i-1] - 2] if i - dp[i-1] >= 2 else 0)
            ans = max(ans, dp[i])
    return ans

栈匹配模板（通用括号问题）：

def parentheses_stack(s):
    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

---

关联题目

• 20-有效的括号 — 基础括号匹配，用栈即可
• 5-最长回文子串 — 子串 DP，区间 DP 经典
• 678-有效的括号字符串 — 含通配符 * 的括号匹配