我们来学习 LeetCode 第 32 题「最长有效括号」。

题目描述

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

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

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

示例 3：
输入：s = ""
输出：0

解题思路

1. 有效括号的性质

有效括号子串必须满足：

• 左右括号数量匹配
• 从左到右扫描时，左括号数量始终不小于右括号数量
• 最终左右括号数量相等

难点：
有效子串可能被无效的括号隔开，比如 "()(()" 中，有效子串是 "()" 而不是 "()(()"，因为中间有未匹配的 '(' 隔开。

2. 动态规划解法（循序渐进）

我们定义 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度（下标从 0 开始）。

情况分析：

情况 1：s[i] = ')' 且 s[i-1] = '('

形如 ...()
那么：
dp[i] = dp[i-2] + 2
解释：在 ...() 中，() 是新增的有效长度 2，再加上 i-2 位置结尾的有效长度。

例子："()"

• i=1, s[0]='(', s[1]=')'
• dp[1] = dp[-1] + 2（dp[-1] 视为 0）
• 所以 dp[1] = 2

情况 2：s[i] = ')' 且 s[i-1] = ')'

形如 ...))
我们需要检查与当前 ')' 匹配的左括号是否存在。

具体步骤：

• 设 j = i - dp[i-1] - 1
j 是与当前 ')' 可能匹配的左括号位置。
• 如果 j >= 0 且 s[j] = '('，说明匹配成功：
  dp[i] = dp[i-1] + 2 + dp[j-1]
  解释：
  • dp[i-1] 是中间已经匹配的长度
  • +2 是新增的 s[j] 与 s[i] 匹配的长度
  • + dp[j-1] 是 j-1 位置结尾的有效长度（连接起来）

例子："()(())"

• 到 i=5 时，s[5]=')', s[4]=')'
• dp[4] = 2（因为 s[3]='(', s[4]=')' 匹配）
• j = 5 - dp[4] - 1 = 5 - 2 - 1 = 2
• s[2] = '('，匹配成功
• dp[5] = dp[4] + 2 + dp[1] = 2 + 2 + 2 = 6（dp[1]=2 因为 s[0]='(', s[1]=')'）

3. 算法步骤

1. 初始化 dp 数组长度为 n，全为 0。
2. 从 i=1 开始遍历字符串（因为 i=0 是左括号的话，不可能形成以它结尾的有效括号串，除非前面有匹配，但 i=0 是起点）。
3. 根据上述两种情况更新 dp[i]。
4. 记录 dp 数组中的最大值。

4. 举例推导

s = ")()())"

最大值 = 4

5. 代码实现（供参考思路）

def longestValidParentheses(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    dp = [0] * n
    max_len = 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)
            max_len = max(max_len, dp[i])
    
    return max_len

6. 复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

这样我们就用动态规划清晰解决了问题，你理解每一步了吗？