LeetCode 32. 最长有效括号题解全解析：动态规划与栈两种 O(n) 算法（doocs/leetcode 多语言实现）

示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 doocs/leetcode 开源仓库中 LeetCode 32. 最长有效括号 题解为核心深入讲解「最长有效括号子串」这一经典困难题的两条 O(n) 求解路线动态规划与栈模拟。读者将掌握状态转移方程的推导逻辑、栈底基准-1的设计动机并可直接对照 Python3、Java、C、Go、TypeScript、Rust、JavaScript、C#、PHP 共 9 种语言的完整可运行实现同时理解仓库中Solution.*与Solution2.*两组源码文件的组织约定。一、题目理解与核心难点1.1 题目描述给定一个只包含(和)的字符串找出最长有效格式正确且连续括号子串的长度。所谓格式正确即左右括号完全匹配每个左括号都有对应的右括号将其闭合例如(()())就是一个格式正确的字符串。注意关键词这里要求的是连续的子串substring而非可跳字符的子序列subsequence。有效段一旦被多余的括号打断就必须从新的起点重新累计这正是本题区别于普通括号配对计数的关键。1.2 示例示例 1输入s (() 输出2 解释最长有效括号子串是 ()示例 2输入s )()()) 输出4 解释最长有效括号子串是 ()()示例 3输入s 输出01.3 数据范围与约束0 s.length 3 * 10^4s[i]为(或)字符串长度上限高达三万意味着 $O(n^2)$ 乃至 $O(n^3)$ 的暴力解法枚举所有子串再用栈逐个判定在时间上不可接受必须设计单趟扫描的线性算法。二、解题思路总览面对最长连续有效段问题突破口有两个重叠子问题以某一位置结尾的最长有效括号段可以由更短的有效段拼接得到。大量子串互相重叠天然适合按结尾位置递推 —— 这是动态规划的切入点。配对过程本身我们需要的不是更高的复杂度而是更贴合配对过程的记录方式 —— 尚未匹配的左括号下标以及上一段失效从何处开始。栈恰好能同时维护这两类信息 —— 这是栈解法的切入点。原题解文档 README.md 正是按这两条路线给出了两种时间、空间均为 $O(n)$ 的标准解法。三、方法一动态规划按结尾位置递推3.1 思考过程枚举每个子串再用栈判定是否有效时间复杂度为 $O(n^2)$ 乃至 $O(n^3)$而 $n \le 3 \times 10^4$无法通过。大量子串互相重叠以某一位置结尾的最长有效括号可以由更短的有效段拼接得到因此可以按结尾位置递推。有效括号串只能以右括号结尾。若当前字符与前一位配成一对长度即为再往前那段加上 $2$若前一位也是右括号则先跨过已经配好的一段再判断这段之前是否还能配上一个左括号。3.2 状态定义定义 $f[i]$ 表示以 $s[i-1]$ 结尾的最长有效括号的长度下标从 1 开始方便处理越界答案即为 $\max\limits_{i1}^n f[i]$。注意当 $i 2$字符串长度不足 2时不可能存在有效括号$f[i] 0$。3.3 状态转移分三类情况讨论当前字符是左括号以 $s[i-1]$ 结尾的最长有效括号长度一定为 $0$即 $f[i] 0$。当前字符是右括号且 $s[i-2]$ 是左括号两者直接配对成()此时长度为再往前那段的最长有效长度加 $2$即 $f[i] f[i-2] 2$。当前字符是右括号且 $s[i-2]$ 也是右括号说明 $s[i-2]$ 本身处于一个已配好的有效段中。先跨过以 $s[i-2]$ 结尾的有效段长度 $f[i-1]$再判断该段之前的位置 $s[i-f[i-1]-2]$ 是否为左括号若为左括号则它能与当前的右括号配对长度为 $f[i-1] 2 f[i-f[i-1]-2]$后半项把更早的有效段也拼接进来。综上状态转移方程为$$ \begin{cases} f[i] 0, \textit{if } s[i-1] (,\ f[i] f[i-2] 2, \textit{if } s[i-1] ) \textit{ and } s[i-2] (,\ f[i] f[i-1] 2 f[i-f[i-1]-2], \textit{if } s[i-1] ) \textit{ and } s[i-2] ) \textit{ and } s[i-f[i-1]-2] (,\ \end{cases} $$最后返回 $\max\limits_{i1}^n f[i]$ 即可。时间复杂度 $O(n)$空间复杂度 $O(n)$其中 $n$ 为字符串长度。3.4 手推演示例理解第三种转移以s ()(())为例按 DP 逐位计算is[i-1]转移依据f[i]1(左括号02)s[0](配对f[0]2 23(左括号04(左括号05)s[3](配对f[3]2 26)s[4])j 6 - f[5] - 1 3s[2](f[5]2f[2] 222 6最终 $f[6]6$即整个()(())都是有效括号串长度为 6。这个例子完整展示了第三种转移如何把内层有效段 新配对 外层有效段三段拼接起来。3.5 多语言实现以下代码与仓库 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs、Solution.php 一一对应可直接运行。Python3class Solution: def longestValidParentheses(self, s: str) - int: n len(s) f [0] * (n 1) for i, c in enumerate(s, 1): if c ): if i 1 and s[i - 2] (: f[i] f[i - 2] 2 else: j i - f[i - 1] - 1 if j and s[j - 1] (: f[i] f[i - 1] 2 f[j - 1] return max(f)Javaclass Solution { public int longestValidParentheses(String s) { int n s.length(); int[] f new int[n 1]; int ans 0; for (int i 2; i n; i) { if (s.charAt(i - 1) )) { if (s.charAt(i - 2) () { f[i] f[i - 2] 2; } else { int j i - f[i - 1] - 1; if (j 0 s.charAt(j - 1) () { f[i] f[i - 1] 2 f[j - 1]; } } ans Math.max(ans, f[i]); } } return ans; } }Cclass Solution { public: int longestValidParentheses(string s) { int n s.size(); int f[n 1]; memset(f, 0, sizeof(f)); for (int i 2; i n; i) { if (s[i - 1] )) { if (s[i - 2] () { f[i] f[i - 2] 2; } else { int j i - f[i - 1] - 1; if (j s[j - 1] () { f[i] f[i - 1] 2 f[j - 1]; } } } } return *max_element(f, f n 1); } };Gofunc longestValidParentheses(s string) int { n : len(s) f : make([]int, n1) for i : 2; i n; i { if s[i-1] ) { if s[i-2] ( { f[i] f[i-2] 2 } else if j : i - f[i-1] - 1; j 0 s[j-1] ( { f[i] f[i-1] 2 f[j-1] } } } return slices.Max(f) }Go 版本通过slices.Max(f)直接取整个 DP 数组的最大值与题解中返回 $\max f[i]$的描述一致该函数需要 Go 1.21 标准库slices支持。TypeScriptfunction longestValidParentheses(s: string): number { const n s.length; const f: number[] new Array(n 1).fill(0); for (let i 2; i n; i) { if (s[i - 1] )) { if (s[i - 2] () { f[i] f[i - 2] 2; } else { const j i - f[i - 1] - 1; if (j s[j - 1] () { f[i] f[i - 1] 2 f[j - 1]; } } } } return Math.max(...f); }Rustimpl Solution { pub fn longest_valid_parentheses(s: String) - i32 { let mut ans 0; let mut f vec![0; s.len() 1]; let chars s.as_bytes(); for i in 2..s.len() { if chars[i - 1] b) { if chars[i - 2] b( { f[i] f[i - 2] 2; } else if (i as i32) - f[i - 1] - 1 0 chars[i - (f[i - 1] as usize) - 2] b( { f[i] f[i - 1] 2 f[i - (f[i - 1] as usize) - 2]; } ans ans.max(f[i]); } } ans } }Rust 版本将字符串转为字节切片s.as_bytes()以避免字符遍历开销并在访问下标前用(i as i32) - f[i - 1] - 1 0显式防止有符号负数下标问题。JavaScript/** * param {string} s * return {number} */ var longestValidParentheses function (s) { const n s.length; const f new Array(n 1).fill(0); for (let i 2; i n; i) { if (s[i - 1] )) { if (s[i - 2] () { f[i] f[i - 2] 2; } else { const j i - f[i - 1] - 1; if (j s[j - 1] () { f[i] f[i - 1] 2 f[j - 1]; } } } } return Math.max(...f); };C#public class Solution { public int LongestValidParentheses(string s) { int n s.Length; int[] f new int[n 1]; int ans 0; for (int i 2; i n; i) { if (s[i - 1] )) { if (s[i - 2] () { f[i] f[i - 2] 2; } else { int j i - f[i - 1] - 1; if (j 0 s[j - 1] () { f[i] f[i - 1] 2 f[j - 1]; } } ans Math.Max(ans, f[i]); } } return ans; } }PHPclass Solution { /** * param string $s * return integer */ function longestValidParentheses($s) { $n strlen($s); $f array_fill(0, $n 1, 0); for ($i 1; $i $n; $i) { if ($s[$i - 1] )) { if ($i 1 $s[$i - 2] () { $f[$i] $f[$i - 2] 2; } else { $j $i - $f[$i - 1] - 1; if ($j $s[$j - 1] () { $f[$i] $f[$i - 1] 2 $f[$j - 1]; } } } } return max($f); } }3.6 源码级实现要点对照仓库源码 Solution.py可以提炼出三个易错点各语言实现的处理方式略有差异DP 数组长度多开一位f [0] * (n 1)让下标从 1 开始对应字符s[i-1]从而天然规避f[i-2]、f[j-1]在边界处的负数下标。Java/C/C#/Go 等语言的实现统一从i 2开始循环因为i 1时不可能产生有效段。第三种转移的双重条件必须同时满足j 0跨过的有效段前面还有字符与s[j-1] (其中j i - f[i-1] - 1。Python/JavaScript/PHP 中利用if j and s[j-1] (的隐式真值判断Java/C# 则显式写j 0 。答案更新时机Java/C# 在循环内用ans Math.max(ans, f[i])边算边更新Python/C/Go/TypeScript/PHP 则在最后对数组整体取最大值两种方式结果等价。四、方法二使用栈记录配对下标4.1 思考过程方法一的 DP 已是 $O(n)$ 时间但转移需区分前一位是否为左括号以及跨过一段有效括号再向前配对下标边界容易遗漏。我们需要的并非更低的复杂度而是更贴合配对过程的记录方式尚未匹配的左括号下标以及上一段失效从何处开始。栈恰好同时维护这两类信息栈底先放入-1作为基准遇左括号压入下标遇右括号弹出若栈空则当前位置成为新基准否则用栈顶更新长度。4.2 算法步骤初始化栈stack [-1]栈底元素-1作为基准用于辅助计算有效括号的长度。遍历字符串对于每个字符如果是左括号(将当前位置下标压入栈。如果是右括号)弹出栈顶元素表示匹配掉一个左括号如果弹出后栈为空说明当前右括号无法匹配任何左括号将当前位置下标压入栈作为新的起点基准如果弹出后栈不为空则当前右括号与栈顶上一个未匹配的左括号或基准之间构成一个有效段计算长度i - stack[-1]并更新最大长度。最终返回最大长度。算法的关键在于维护一条基线栈内存放的是左括号的索引通过弹出和压入的操作来更新有效括号子串的长度。时间复杂度 $O(n)$空间复杂度 $O(n)$。4.3 手推演示例以s )()())为例下标 i字符操作栈内容当前最长初始--[-1]00)pop 后栈空push 0[0]01(push 1[0, 1]02)pop栈非空2 - 0 2[0]23(push 3[0, 3]24)pop栈非空4 - 0 4[0]45)pop 后栈空push 5[5]4答案 4 对应子串()()与题目示例一致。注意下标 0 的孤立右括号被保留在栈中作为新基准它把后面的有效段与更早的历史隔断了 —— 这正是连续子串要求的体现。4.4 多语言实现以下代码与仓库 Solution2.py、Solution2.go、Solution2.ts、Solution2.rs、Solution2.js、Solution2.php 一一对应。Python3class Solution: def longestValidParentheses(self, s: str) - int: stack [-1] ans 0 for i in range(len(s)): if s[i] (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ansGofunc longestValidParentheses(s string) int { ans : 0 stack : []int{-1} for i, v : range s { if v ( { stack append(stack, i) } else { stack stack[:len(stack)-1] if len(stack) 0 { stack append(stack, i) } else { if ans i-stack[len(stack)-1] { ans i - stack[len(stack)-1] } } } } return ans }TypeScriptfunction longestValidParentheses(s: string): number { let max_length: number 0; const stack: number[] [-1]; for (let i 0; i s.length; i) { if (s.charAt(i) () { stack.push(i); } else { stack.pop(); if (stack.length 0) { stack.push(i); } else { max_length Math.max(max_length, i - stack[stack.length - 1]); } } } return max_length; }Rustimpl Solution { pub fn longest_valid_parentheses(s: String) - i32 { let mut stack vec![-1]; let mut res 0; for (i, c) in s.bytes().enumerate() { if c b( { stack.push(i as i32); } else { stack.pop().unwrap(); if stack.is_empty() { stack.push(i as i32); } else { res std::cmp::max(res, (i as i32) - stack.last().unwrap()); } } } res } }JavaScript/** * param {string} s * return {number} */ var longestValidParentheses function (s) { let ans 0; const stack [-1]; for (i 0; i s.length; i) { if (s.charAt(i) () { stack.push(i); } else { stack.pop(); if (stack.length 0) { stack.push(i); } else { ans Math.max(ans, i - stack[stack.length - 1]); } } } return ans; };PHPclass Solution { /** * param string $s * return integer */ function longestValidParentheses($s) { $stack []; $maxLength 0; array_push($stack, -1); for ($i 0; $i strlen($s); $i) { if ($s[$i] () { array_push($stack, $i); } else { array_pop($stack); if (empty($stack)) { array_push($stack, $i); } else { $length $i - end($stack); $maxLength max($maxLength, $length); } } } return $maxLength; } }4.5 源码级实现要点对照仓库源码 Solution2.py栈方法的实现细节初始化必须带-1它作为虚拟前哨使得形如()的完整有效段从下标 0 开始也能算出长度i - (-1)若去掉它()这类整串有效的情况会被漏算。弹出后栈空的处理此时当前右括号是孤立的必须把它压入栈作为新基准否则后续有效段的长度会被错误地跨过这段无效前缀计算。长度计算用i - stack[-1]栈顶始终是当前有效段左侧最近的未匹配位置两者之差即为有效段长度每算出一个长度就与全局最大值取 max。五、两种解法对比与选型建议维度动态规划方法一栈模拟方法二核心思想以结尾位置为状态重叠子问题递推用栈记录未匹配左括号下标与失效基准时间复杂度$O(n)$$O(n)$空间复杂度$O(n)$$O(n)$状态转移需区分前一位是左括号还是右括号边界较难把握只需弹出/压入配对过程直观代表源码Solution.py 等Solution.*Solution2.py 等Solution2.*适用场景熟悉 DP 递推、需要显式状态定义的读者理解配对过程直观、实现更不易出错两种方法性能相同选择哪条路线主要看个人偏好DP 写法更数学化考验状态设计与下标边界把握栈写法更模拟化直接复现括号配对的物理过程。原题解文档 README.md 同时给出两条路线正是为了让读者从两个角度理解同一问题。六、仓库源码组织约定与延伸阅读doocs/leetcode 仓库对同一题目的多种解法采用统一命名约定第一种解法存放为Solution.ext第二种解法存放为Solution2.ext。以本题为例动态规划解法Solution.py、Solution.java、Solution.cpp、Solution.cs、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.php栈解法Solution2.py、Solution2.go、Solution2.ts、Solution2.rs、Solution2.js、Solution2.php这种约定在整个仓库中一致适用例如 01.02.Check Permutation、08.01.Three Steps Problem 等目录同样存在Solution2.*文件读者在阅读任意题目时可以据此快速定位不同解法。本题的英文版题解位于 README_EN.md。从源码结构看本题还有进一步探索的空间例如DP 状态只依赖 $f[i-1]$、$f[i-2]$ 与 $f[j-1]$ 等前序值但 $j$ 可能回溯到很靠前的位置因此不能简单压缩为常数空间栈方法则天然记录了有效段的边界信息可进一步扩展用于输出最长有效子串本身。读者可基于上述两组源码自行验证不同边界输入如全左括号、全右括号、空串、交替串等下的行为以加深对两种算法的理解。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐InterviewGuide 精讲LeetCode 32 最长有效括号从错误解法到 O(n) 双变量计数与动态规划全解InterviewGuide 精讲LeetCode 32 最长有效括号从错误解法到 O n 双变量计数与动态规划全解 本文是《阿秀的学习笔记》之「精选力扣文档教程知识库AlgoNote 题解精讲 | LeetCode 0032「最长有效括号」动态规划与栈双解法深度解析AlgoNote 题解精讲 | LeetCode 0032「最长有效括号」动态规划与栈双解法深度解析 本文是 AlgoNote「算法通关手册」系列题解之一围教程教育LeetCode 1871 Jump Game VII 四解法深度解析记忆化、BFS 与两种 O(n) 动态规划附 leetcode 仓库多语言实现LeetCode 1871 Jump Game VII 四解法深度解析记忆化、BFS 与两种 O n 动态规划附 leetcode 仓库多语言实现 本指南示例工程上一篇Redwood性能优化10个提升跨平台应用响应速度的关键技巧下一篇终极指南如何使用baseAdapter轻松实现Android多类型Item布局创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考