最长有效括号 题目描述 给定一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 示例： 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" ，长度为 4。 解题过程 1. 问题分析 有效括号子串需满足： 每个左括号 '(' 必须有对应的右括号 ')' 匹配。 匹配的括号对必须是连续的，例如 "()()" 是连续有效，而 "()(" 不是有效子串。 目标是找到 最长连续有效子串 的长度。 2. 动态规划定义 定义 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度（索引从 0 开始）。 若 s[i] 是 '(' ，则不可能以 '(' 结尾形成有效括号，故 dp[i] = 0 。 若 s[i] 是 ')' ，需检查前一个字符的情况，具体分类讨论： 3. 状态转移分析 情况 1 ： s[i] = ')' 且 s[i-1] = '(' 形如 "...()" ，此时： dp[i] = dp[i-2] + 2 解释： "()" 长度为 2，再加上前面可能存在的有效长度 dp[i-2] （如果 i-2 >= 0 ）。 情况 2 ： s[i] = ')' 且 s[i-1] = ')' 形如 "...))" ，此时需检查 s[i - dp[i-1] - 1] 是否为 '(' ： 设 j = i - dp[i-1] - 1 ，若 j >= 0 且 s[j] = '(' ，则说明当前 ')' 与位置 j 的 '(' 匹配。 匹配后，当前有效长度为： dp[i] = dp[i-1] + 2 + dp[j-1] 解释： dp[i-1] 是紧挨着当前 ')' 之前的有效长度。 +2 是新增的匹配括号对 ( ) 。 + dp[j-1] 是 j-1 位置可能存在的有效长度（如果 j-1 >= 0 ）。 4. 示例推导 以 s = ")()())" 为例（索引 0~5）： 初始 dp = [0,0,0,0,0,0] i=0 : s[0]=')' ，前无字符， dp[0]=0 i=1 : s[1]='(' ， dp[1]=0 i=2 : s[2]=')' ，且 s[1]='(' （情况 1）， dp[2] = dp[0] + 2 = 0+2=2 i=3 : s[3]='(' ， dp[3]=0 i=4 : s[4]=')' ，且 s[3]='(' （情况 1）， dp[4] = dp[2] + 2 = 2+2=4 i=5 : s[5]=')' ，且 s[4]=')' （情况 2）： j = 5 - dp[4] - 1 = 5 - 4 - 1 = 0 s[0]=')' 不是 '(' ，匹配失败， dp[5]=0 最终 dp = [0,0,2,0,4,0] ，最大值为 4。 5. 算法实现要点 遍历 i 从 0 到 n-1 。 仅当 s[i]=')' 时处理两种情况。 注意下标越界判断（如 i-2 、 j-1 ）。 时间复杂度 O(n)，空间复杂度 O(n)。 6. 关键理解 dp[i] 只记录以 i 结尾的有效长度，全局最大值需在遍历中记录。 情况 2 是难点：通过 j = i - dp[i-1] - 1 跳转到可能匹配的左括号位置，并连接起之前的有效段。