企业官网建设流程全解析

• 示例工程

本文以 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 = "" 输出：0

1.3 数据范围与约束

• 0 <= s.length <= 3 * 10^4
• s[i]为'('或')'

字符串长度上限高达三万，意味着 $O(n^2)$ 乃至 $O(n^3)$ 的暴力解法（枚举所有子串再用栈逐个判定）在时间上不可接受，必须设计单趟扫描的线性算法。

二、解题思路总览

面对"最长连续有效段"问题，突破口有两个：

1. 重叠子问题：以某一位置结尾的最长有效括号段，可以由更短的有效段拼接得到。大量子串互相重叠，天然适合按结尾位置递推 —— 这是动态规划的切入点。
2. 配对过程本身：我们需要的不是更高的复杂度，而是更贴合配对过程的记录方式 —— 尚未匹配的左括号下标，以及上一段失效从何处开始。栈恰好能同时维护这两类信息 —— 这是栈解法的切入点。

原题解文档 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_{i=1}^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_{i=1}^n f[i]$ 即可。时间复杂度 $O(n)$，空间复杂度 $O(n)$，其中 $n$ 为字符串长度。

3.4 手推演示例：理解第三种转移

以s = "()(())"为例，按 DP 逐位计算：

最终 $f[6]=6$，即整个"()(())"都是有效括号串，长度为 6。这个例子完整展示了第三种转移如何把"内层有效段 + 新配对 + 外层有效段"三段拼接起来。

3.5 多语言实现

以下代码与仓库 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs、Solution.php 一一对应，可直接运行。

Python3

class 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)

Java

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.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; } }

C++

class 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); } };

Go

func longestValidParentheses(s string) int { n := len(s) f := make([]int, n+1) 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支持。

TypeScript

function 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); }

Rust

impl 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; } }

PHP

class 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，可以提炼出三个易错点，各语言实现的处理方式略有差异：

1. DP 数组长度多开一位：f = [0] * (n + 1)，让下标从 1 开始对应字符s[i-1]，从而天然规避f[i-2]、f[j-1]在边界处的负数下标。Java/C++/C#/Go 等语言的实现统一从i = 2开始循环，因为i = 1时不可能产生有效段。
2. 第三种转移的双重条件：必须同时满足j > 0（跨过的有效段前面还有字符）与s[j-1] == '('，其中j = i - f[i-1] - 1。Python/JavaScript/PHP 中利用if j and s[j-1] == "("的隐式真值判断，Java/C# 则显式写j > 0 &&。
3. 答案更新时机：Java/C# 在循环内用ans = Math.max(ans, f[i])边算边更新，Python/C++/Go/TypeScript/PHP 则在最后对数组整体取最大值，两种方式结果等价。

四、方法二：使用栈（记录配对下标）

4.1 思考过程

方法一的 DP 已是 $O(n)$ 时间，但转移需区分"前一位是否为左括号"以及"跨过一段有效括号再向前配对"，下标边界容易遗漏。我们需要的并非更低的复杂度，而是更贴合配对过程的记录方式：尚未匹配的左括号下标，以及上一段失效从何处开始。栈恰好同时维护这两类信息：栈底先放入-1作为基准，遇左括号压入下标，遇右括号弹出；若栈空则当前位置成为新基准，否则用栈顶更新长度。

4.2 算法步骤

1. 初始化栈stack = [-1]：栈底元素-1作为基准，用于辅助计算有效括号的长度。
2. 遍历字符串，对于每个字符：
   • 如果是左括号(，将当前位置下标压入栈。
   • 如果是右括号)，弹出栈顶元素，表示匹配掉一个左括号：
     • 如果弹出后栈为空，说明当前右括号无法匹配任何左括号，将当前位置下标压入栈，作为新的起点基准；
     • 如果弹出后栈不为空，则当前右括号与栈顶（上一个未匹配的左括号或基准）之间构成一个有效段，计算长度i - stack[-1]并更新最大长度。
3. 最终返回最大长度。

算法的关键在于维护一条"基线"：栈内存放的是左括号的索引，通过弹出和压入的操作来更新有效括号子串的长度。时间复杂度 $O(n)$，空间复杂度 $O(n)$。

4.3 手推演示例

以s = ")()())"为例：

答案 4 对应子串"()()"，与题目示例一致。注意下标 0 的孤立右括号被保留在栈中作为新基准，它把后面的有效段与更早的历史"隔断"了 —— 这正是"连续子串"要求的体现。

4.4 多语言实现

以下代码与仓库 Solution2.py、Solution2.go、Solution2.ts、Solution2.rs、Solution2.js、Solution2.php 一一对应。

Python3

class 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 ans

Go

func 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 }

TypeScript

function 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; }

Rust

impl 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; };

PHP

class 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. 初始化必须带-1：它作为"虚拟前哨"，使得形如"()"的完整有效段（从下标 0 开始）也能算出长度i - (-1)；若去掉它，"()"这类整串有效的情况会被漏算。
2. 弹出后栈空的处理：此时当前右括号是"孤立"的，必须把它压入栈作为新基准，否则后续有效段的长度会被错误地跨过这段无效前缀计算。
3. 长度计算用i - stack[-1]：栈顶始终是"当前有效段左侧最近的未匹配位置"，两者之差即为有效段长度；每算出一个长度就与全局最大值取 max。

五、两种解法对比与选型建议

两种方法性能相同，选择哪条路线主要看个人偏好：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$ 可能回溯到很靠前的位置，因此不能简单压缩为常数空间；栈方法则天然记录了有效段的边界信息，可进一步扩展用于输出最长有效子串本身。读者可基于上述两组源码自行验证不同边界输入（如全左括号、全右括号、空串、交替串等）下的行为，以加深对两种算法的理解。

• 示例工程