好的，我们这次来详细讲解 LeetCode 第 32 题「最长有效括号」（Longest Valid Parentheses）。

1. 题目描述

难度：困难
标签：栈、字符串、动态规划

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

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

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

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

提示：

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

2. 理解题意与有效括号性质

首先，我们要明确什么是有效括号：

• 每个左括号必须有对应的右括号匹配。
• 匹配时左括号必须在右括号之前。
• 有效括号串内，任意前缀中左括号数量 ≥ 右括号数量，且最终左右括号数量相等。

连续有效括号子串：
是原始字符串的一个连续子串，且该子串本身是有效括号串。

目标：
不是求有多少个有效括号对，而是求最长有效括号子串的长度。

3. 思路分析

3.1 暴力法（不可行）

枚举所有子串，用栈判断是否有效。
复杂度 O(n³) 或 O(n²)（用计数器可 O(n) 判断一个子串是否有效），但 n 最大 3 万，会超时。
所以必须找 O(n) 解法。

3.2 动态规划解法（推荐掌握）

定义 dp[i]：表示以 s[i] 结尾的最长有效括号子串的长度。
注意：有效括号串一定以 ) 结尾，所以遇到 '(' 时 dp[i] = 0。

情况分析：

1. s[i] = ')' 且 s[i-1] = '('
   形如 ...()
   那么 dp[i] = dp[i-2] + 2
   即把这对 () 加上，再连上前面可能有的有效串。

2. s[i] = ')' 且 s[i-1] = ')'
   形如 ...))
   如果 s[i - dp[i-1] - 1] = '('，说明当前 ) 可以和前面的一个 '(' 匹配：

   • 先找到与当前 ) 对应的 '(' 位置：j = i - dp[i-1] - 1
   • 如果 j >= 0 且 s[j] == '('，则可以匹配：
     dp[i] = dp[i-1] + 2 + dp[j-1]
     解释：dp[i-1] 是中间的有效长度，+2 是新匹配的一对，+ dp[j-1] 是 '(' 前面的有效长度。

边界处理：
注意下标不要越界，比如 i-2 可能小于 0，判断一下。

举例：s = "()(())"
i=0: '(' -> 0
i=1: ')' 且 s[0]='(' -> dp[1] = dp[-1] (0) + 2 = 2
i=2: '(' -> 0
i=3: '(' -> 0
i=4: ')' 且 s[3]='(' -> dp[4] = dp[2] (0) + 2 = 2
i=5: ')' 且 s[4]=')'，j=5-dp[4]-1=5-2-1=2，s[2]='(' -> 匹配
dp[5] = dp[4] (2) + 2 + dp[1] (2) = 2+2+2=6

3.3 栈解法（直观）

用栈保存下标，初始压入 -1 作为“最后一个未匹配的右括号”的标记（哨兵）。

遍历字符串：

• 遇到 '('，下标入栈。
• 遇到 ')'：
  1. 弹出栈顶（匹配一个左括号）。
  2. 如果栈为空，说明当前右括号没有匹配的左括号，将当前下标入栈（作为新的哨兵，表示从这里开始不连续）。
  3. 如果栈不空，当前有效长度 = 当前下标 - 栈顶下标，更新最大长度。

原理：栈顶始终是“最后一个未能匹配的右括号”或哨兵 -1，这样当前 ) 匹配后，有效串长度就是从上一个未匹配位置到当前位置。

举例：s = ")()())"
栈初始：[-1]
i=0: ')' -> 弹出 -1，栈空 -> 压入 0（新哨兵）
i=1: '(' -> 压入 1
i=2: ')' -> 弹出 1，栈顶 0，长度=2-0=2，max=2
i=3: '(' -> 压入 3
i=4: ')' -> 弹出 3，栈顶 0，长度=4-0=4，max=4
i=5: ')' -> 弹出 0，栈空 -> 压入 5

结果 max=4。

3.4 双指针法（空间 O(1)）

从左到右扫描：

• 记录左右括号数量 left, right。
• 如果 left == right，更新最大长度 = 2*left。
• 如果 right > left，重置 left=right=0（因为后面不可能与前面连续有效）。

但这样会漏掉 "(()" 这种情况（左括号一直多，不会相等），所以再从右到左扫描一遍，条件对称：

• 如果 left == right，更新最大长度。
• 如果 left > right，重置。

两遍扫描取最大值。

4. 详细讲解（以动态规划为例）

我们实现 动态规划 版本，因为它思路清晰且是常见思路。

步骤：

1. 创建 dp 数组，长度 n，初始化为 0。
2. 从 i=1 开始遍历（因为 i=0 是 '(' 则 0，是 ')' 也不可能匹配）。
3. 如果 s[i] == ')'：
   • 如果 s[i-1] == '('：
     dp[i] = (i>=2 ? dp[i-2] : 0) + 2
   • 如果 s[i-1] == ')'：
     令 j = i - dp[i-1] - 1
     如果 j>=0 且 s[j]=='('：
     dp[i] = dp[i-1] + 2 + (j>=1 ? dp[j-1] : 0)
4. 遍历过程中记录 dp[i] 的最大值。

例子：s = "()(())"

i=0: dp[0]=0
i=1: s[1]=')'，s[0]='(' -> dp[1] = dp[-1]?0 + 2 = 2, max=2
i=2: '(' -> 0
i=3: '(' -> 0
i=4: ')'，s[3]='(' -> dp[4] = dp[2] (0) + 2 = 2, max=2
i=5: ')'，s[4]=')'，j=5-dp[4]-1=2，s[2]='(' ->
dp[5] = dp[4] (2) + 2 + dp[1] (2) = 6, max=6

结果=6。

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] == '(':
                # 形如 ...()
                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)
            max_len = max(max_len, dp[i])
    
    return max_len

6. 复杂度分析

• 时间复杂度：O(n)，一次遍历。
• 空间复杂度：O(n)，dp 数组。

7. 总结

• 关键理解：dp[i] 表示以 i 结尾的最长有效括号子串长度。
• 分情况讨论当前字符是 ) 时，前一个字符是 '(' 还是 ')'。
• 动态规划比栈法稍难想，但代码简洁。栈法更直观。
• 该题是处理括号类问题的进阶，掌握后对类似子串匹配问题有很大帮助。

需要我再用栈的方法详细演示一遍吗？这样可以对比两种思路。