最长有效括号

1. 题目描述

给你一个只包含 '(' 和 ')' 的字符串，请你找出最长有效括号子串的长度。

• 有效括号字符串满足：
  • 每个左括号 '(' 都有一个对应的右括号 ')'。
  • 左括号必须在对应的右括号之前。
  • 有效括号字符串必须是连续的。

示例 1

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

示例 2

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

示例 3

输入：s = ""
输出：0

2. 思路分析

这个问题是“最长有效括号子串”，不是子序列，所以必须是连续的一段。
我们可以用线性动态规划解决，核心是定义状态和转移方程。

3. 定义状态

定义 dp[i] 表示以字符 s[i] 结尾的最长有效括号子串的长度。
注意：

• 如果 s[i] 是 '('，那么以它结尾的子串不可能是有效括号（因为右括号才能结尾有效串），所以 dp[i] = 0。
• 我们只需要考虑 s[i] == ')' 的情况。

4. 状态转移

情况 1：s[i-1] == '('
形如 ...()，那么 dp[i] = dp[i-2] + 2（如果 i-2 >= 0，否则 dp[i] = 2）。

例子：
s = "()"，i=1，s[0]='('，dp[1] = 0 + 2 = 2。

情况 2：s[i-1] == ')'
形如 ...))，那么我们要检查 s[i - dp[i-1] - 1] 这个位置。
解释：dp[i-1] 是以 s[i-1] 结尾的有效括号长度，那么它前面一个字符的位置是 i - dp[i-1] - 1。

如果这个字符是 '('，就可以和 s[i]=')' 匹配。此时：

1. 匹配上了，长度至少增加 2。
2. 还要加上匹配位置前面的有效括号长度，即 dp[i - dp[i-1] - 2]。

所以：

dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]

前提是 i - dp[i-1] - 1 >= 0 且 s[i - dp[i-1] - 1] == '('。

例子：
s = "()(())"，计算 i=5（最后一个 ')'）。

• dp[4] 是以 s[4]=')' 结尾的有效括号长度，s[3]='(' 和 s[4]=')' 匹配，dp[4] = 2。
• 检查 i - dp[4] - 1 = 5 - 2 - 1 = 2，s[2] = '('，匹配成功。
• 长度增加 2，再加上 dp[1]（i - dp[4] - 2 = 1 处的值）。dp[1]=2。
• 所以 dp[5] = 2 + 2 + 2 = 6（整个字符串长度 6，全有效）。

5. 边界处理

• 如果 i - dp[i-1] - 1 或 i - dp[i-1] - 2 越界，就取 0。
• 初始 dp[0] = 0。

6. 算法步骤

1. 初始化 dp 数组长度为 n，全部为 0。
2. 遍历 i 从 1 到 n-1：
   • 如果 s[i] == ')'：
     • 如果 s[i-1] == '('：

       dp[i] = (dp[i-2] if i >= 2 else 0) + 2
       

     • 如果 s[i-1] == ')' 且 i - dp[i-1] - 1 >= 0 且 s[i - dp[i-1] - 1] == '('：

       prev_len = dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0
       dp[i] = dp[i-1] + 2 + prev_len
       

3. 遍历过程中记录最大的 dp[i] 作为答案。

7. 示例推演

以 s = ")()())" 为例：

i=0: s[0]=')'，但 s[-1] 不存在，dp[0]=0
i=1: s[1]='(' → dp[1]=0
i=2: s[2]=')' 且 s[1]='(' → dp[2]=dp[0]+2=2
i=3: s[3]='(' → dp[3]=0
i=4: s[4]=')' 且 s[3]='(' → dp[4]=dp[2]+2=4
i=5: s[5]=')' 且 s[4]=')' → 
     i - dp[4] - 1 = 0, s[0]=')' 不匹配 '(' → dp[5]=0

最大 dp 值是 4，对应子串 s[1:5] 即 "()()"。

8. 复杂度分析

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

9. 核心要点

• 定义 dp[i] 为以 s[i] 结尾的最长有效括号子串长度。
• 对 ')' 分两种情况讨论，核心是找到与当前 ')' 匹配的左括号位置。
• 匹配成功后，要加上匹配括号前面的有效长度。

这样，我们就用动态规划在线性时间内解决了最长有效括号子串问题。