LeetCode 32最长有效括号题解，如何为？

题目链接：32. 最长有效括号 目录1. 题目解读2. 解题思路讨论解法一：栈 (Stack) —— 最直观解法二：动态规划 (Dynamic Programming)解法三：双指针（两次遍历）—— 空间最优3. 代码实现栈解法动态规划解法双指针解法 - 空间 O(1)4. 复杂度分析5. 总结与建议 1. 题目解读 题目含义： 给定一个只包含 '(' 和 ')' 的字符串，我们需要找到其中最长的、连续的、且格式正确的括号子串的长度。 什么是“格式正确”？ 左括号 '(' 必须有对应的右括号 ')' 闭合。 括号必须成对出现，且嵌套顺序正确。 正确示例："()", "(())", "()()", "(()())" 错误示例："(", ")", "(()", ")(" 关键点： 必须是子串（连续的一段），不能是子序列（挑着选）。 我们需要返回的是长度，而不是子串本身。 示例分析： 输入："(()" 索引 0,1 是 "()" (有效，长度 2) 索引 0,1,2 是 "(()" (无效) 最长有效长度是 2。 输入：")()())" 索引 1,2 是 "()" 索引 1,2,3,4 是 "()()" (有效，长度 4) 最长有效长度是 4。 2. 解题思路讨论 这道题是经典的字符串处理问题，主要有三种主流解法：栈（Stack）、动态规划（DP） 和 双指针（两次遍历）。它们的时间复杂度都是 \(O(n)\)，但空间复杂度和思维难度不同。 解法一：栈 (Stack) —— 最直观 核心思想： 利用栈来跟踪括号的下标。栈底始终保存“最后一个无法匹配的右括号的索引”或者“初始基准点”。 具体步骤： 初始化一个栈，放入 -1。 为什么放 -1？ 这是一个基准点。如果有效括号从字符串索引 0 开始（例如 "()"），计算长度时需要用 当前索引 - 栈顶索引。如果栈顶是 -1，长度就是 1 - (-1) = 2，计算正确。 遍历字符串： 遇到 '('：将当前索引压入栈。表示这是一个待匹配的左括号。 遇到 ')'： 弹出栈顶元素（表示匹配了一个左括号，或者弹出了之前的基准点）。 如果栈为空：说明当前的 ')' 没有左括号可以匹配，它成为了新的“无效边界”。将当前索引压入栈，作为新的基准点。 如果栈不为空：说明当前的 ')' 成功匹配了栈中对应的 '('。此时，当前索引 - 栈顶索引 就是以当前 ')' 结尾的最长有效括号长度。更新最大长度。 图解示例 ")()())"： 初始：stack = [-1], max_len = 0 i=0, s[0]=')': pop(-1) -> stack 空。push(0)。stack = [0] i=1, s[1]='(': push(1)。stack = [0, 1] i=2, s[2]=')': pop(1) -> stack=[0]。不为空。len = 2 - 0 = 2。max_len = 2 i=3, s[3]='(': push(3)。stack = [0, 3] i=4, s[4]=')': pop(3) -> stack=[0]。不为空。len = 4 - 0 = 4。max_len = 4 i=5, s[5]=')': pop(0) -> stack 空。push(5)。stack = [5] 结果：4 优点： 逻辑直观，符合括号匹配的直觉。 缺点： 需要 \(O(n)\) 的额外空间。 解法二：动态规划 (Dynamic Programming) 核心思想： 定义 dp[i] 为以索引 i 结尾的最长有效括号子串的长度。 状态转移： 如果 s[i] == '('：dp[i] = 0（有效括号不可能以左括号结尾）。 如果 s[i] == ')'： 情况 A：s[i-1] == '('。形成了 "(...())" 结构。 dp[i] = dp[i-2] + 2 （如果 i>=2，否则就是 2）。 情况 B：s[i-1] == ')'。形成了 "(...))" 结构。 我们需要跳过前面已经匹配好的有效括号，去找更前面的左括号。 前面有效长度是 dp[i-1]，所以对应的左括号位置在 i - dp[i-1] - 1。 如果 s[i - dp[i-1] - 1] == '('，则匹配成功。 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（加上再前面的有效长度）。 优点： 标准的 DP 思路，适合练习动态规划。 缺点： 状态转移方程较复杂，容易写错边界条件。