最长有效括号问题 题目描述 给定一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。例如，输入 "(()"，输出 2（有效子串为 "()"）；输入 ")()())"，输出 4（有效子串为 "()()"）。 解题思路 该问题的核心在于识别连续的有效括号序列，并记录其最大长度。有效括号序列需满足： 左右括号数量相等； 从左到右遍历时，左括号数始终不小于右括号数。 步骤分解 1. 暴力法（需优化） 枚举所有可能的子串，检查其是否有效。 时间复杂度 O(n³)（枚举子串 O(n²)，检查有效性 O(n)），不可行。 2. 动态规划解法 定义 dp[i] 表示以第 i 个字符结尾的最长有效括号子串长度。 初始化 ： dp 数组全为 0。 情况分析 ： 若 s[i] = ')' 且 s[i-1] = '(' （形如 "...()"），则 dp[i] = dp[i-2] + 2 。 若 s[i] = ')' 且 s[i-1] = ')' （形如 "...))"），需检查 s[i - dp[i-1] - 1] 是否为 '('： 若是，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] （合并前方有效序列）。 示例 ： 对 s = "()(())" ，计算过程如下： i=1: "()" → dp[1] = 2 i=5: 检查 s[5-1]=')' ，向前跳 dp[4]=2 位到 s[2] ，发现 s[2]='(' ，则 dp[5] = 2 + 2 + dp[1] = 6 。 3. 栈解法（更直观） 栈的作用 ：记录未匹配的括号下标。 算法步骤 ： 初始化栈，压入 -1 作为哨兵（表示有效序列的起始前一位）。 遍历字符串： 遇 '('：压入当前下标。 遇 ')'：弹出栈顶（表示匹配一个左括号），若栈为空则压入当前下标（更新哨兵），否则计算当前有效长度 i - stack.top() 。 持续更新最大长度。 示例 ： s = ")()())" ，栈变化如下： i=0: ')' → 栈初始为 [-1] ，弹出 -1 后栈空，压入 0 → 栈 [0] i=1: '(' → 压入 1 → 栈 [0,1] i=2: ')' → 弹出 1，栈顶为 0，长度=2-0=2 → 更新最大长度=2 i=3: '(' → 压入 3 → 栈 [0,3] i=4: ')' → 弹出 3，栈顶为 0，长度=4-0=4 → 更新最大长度=4 i=5: ')' → 弹出 0，栈空，压入 5 → 栈 [5] 4. 双指针解法（空间优化） 左右遍历两次： 从左到右：统计左右括号数，相等时更新长度，右括号多时重置计数。 从右到左：同理，左括号多时重置。 避免漏掉如 "(()" 的案例（左括号始终多，需反向遍历）。 关键点总结 动态规划 ：需处理嵌套括号（如 (()) ）和并列括号（如 ()() ）的合并。 栈解法 ：哨兵索引是核心，用于处理边界情况。 双指针 ：通过双向遍历保证所有有效序列被覆盖。 复杂度分析 时间复杂度：O(n) 空间复杂度：O(n)（栈或DP数组）或 O(1)（双指针）