括号匹配的最大长度问题 题目描述 给定一个只包含字符 '(' 和 ')' 的字符串 s ，找出其中最长的有效（格式正确）括号子串的长度。 有效括号字符串需满足： 每个左括号 '(' 必须有对应的右括号 ')' 匹配。 括号匹配需按正确顺序（即 ")(" 无效）。 示例： 输入： s = "(()" ，输出： 2 （最长有效子串为 "()" ）。 输入： s = ")()())" ，输出： 4 （最长有效子串为 "()()" ）。 解题步骤 1. 定义状态 设 dp[i] 表示以字符 s[i] 结尾的最长有效括号子串的长度。 目标：遍历所有 i ，取 max(dp[i]) 作为答案。 2. 分析转移规则 情况1 ： s[i] = ')' 且 s[i-1] = '(' （形如 "...()" ）。 此时 dp[i] = dp[i-2] + 2 （若 i-2 存在，否则为 2 ）。 例如： "()" 中 i=1 ， dp[1] = 0 + 2 = 2 。 情况2 ： s[i] = ')' 且 s[i-1] = ')' （形如 "...))" ）。 检查 i - dp[i-1] - 1 位置的字符： 若该位置为 '(' ，则与当前 ')' 匹配。 此时 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] 。 dp[i-1] + 2 ：当前匹配的括号对长度。 加上 dp[i - dp[i-1] - 2] ：匹配对之前的有效子串长度（若存在）。 示例： "()(())" ，当 i=5 （最后一个 ')' ）： dp[4] = 2 （子串 "(())" 的前4位已处理）。 检查 i - dp[4] - 1 = 5 - 2 - 1 = 2 ， s[2] = '(' ，匹配成功。 dp[5] = dp[4] + 2 + dp[1] = 2 + 2 + 2 = 6 。 3. 初始化与边界处理 dp 数组初始化为 0 。 若 i=0 或 s[i] = '(' ，则 dp[i] = 0 （有效子串不能以 '(' 结尾）。 4. 示例推导 以 s = ")()())" 为例： | i | s[ i] | 情况分析 | dp[ i ] | 说明 | |---|------|----------|-------|------| | 0 | ')' | 不匹配 | 0 | 无效起始 | | 1 | '(' | 忽略 | 0 | 左括号结尾无效 | | 2 | ')' | 情况1 | 2 | s[1]='(' ，匹配 "()" | | 3 | '(' | 忽略 | 0 | 左括号结尾无效 | | 4 | ')' | 情况2 | 4 | i=4 ，检查 i-dp[3]-1=3 ，但 s[3]='(' 匹配， dp[4]=dp[3]+2+dp[1]=0+2+2=4 | | 5 | ')' | 情况2 | 2 | i=5 ，检查 i-dp[4]-1=0 ， s[0]=')' 不匹配， dp[5]=0 | 最大值为 max(0,2,0,4,2)=4 。 5. 算法实现要点 遍历 i 从 0 到 n-1 ，按上述规则更新 dp[i] 。 时间复杂度： O(n) ，空间复杂度： O(n) 。 通过逐步分析状态转移，可准确计算最长有效括号子串的长度。