延安市网站建设_网站建设公司_门户网站_seo优化

Java版LeetCode热题100之最长有效括号：三种解法深度剖析与算法思维升华

本文全面解析 LeetCode 第32题「最长有效括号」，这是一道考察字符串处理、动态规划、栈应用及双指针技巧的经典难题。文章涵盖题目理解、三种主流解法（DP、栈、双指针）、代码实现、复杂度分析、面试高频问题、实际应用场景及延伸思考，是一篇面向中高级开发者的高质量技术博客。

一、原题回顾

题目编号：LeetCode 32
题目名称：最长有效括号（Longest Valid Parentheses）
难度等级：困难（Hard）

题目描述

给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。

有效括号字符串需满足：

• 空字符串是有效的；
• 若 A 是有效字符串，则 “(A)” 也是有效的；
• 若 A 和 B 都是有效字符串，则 AB 也是有效的。

示例

示例 1： 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"，位于索引 1-2。 示例 2： 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"，位于索引 1-4。 示例 3： 输入：s = "" 输出：0 解释：空字符串，无有效子串。

约束条件

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

二、原题分析

2.1 问题本质

本题要求找到最长的连续有效括号子串，而非子序列。关键点：

• 连续性：必须是子串（substring），不能跳过字符；
• 有效性：括号必须正确匹配，即每个)都有对应的(在其左侧；
• 最大化长度：只需返回长度，不要求具体子串。

2.2 直观误区

最朴素的想法是：枚举所有子串，检查是否有效。但时间复杂度为 O(n³)（O(n²) 子串 × O(n) 验证），对于n=30000显然不可行。

因此，我们需要更高效的策略。本题有三种经典解法：

1. 动态规划（DP）：记录以每个位置结尾的最长有效长度；
2. 栈（Stack）：利用栈模拟匹配过程，记录边界；
3. 双指针（Two Pass）：贪心统计左右括号数量，正反两次扫描。

每种方法都体现了不同的算法思想，值得深入学习。

三、答案构思：方法一 —— 动态规划

3.1 核心思想

定义dp[i]表示：以索引i结尾的最长有效括号子串的长度。

关键观察：有效子串必以')'结尾，故若s[i] == '('，则dp[i] = 0。

3.2 状态转移方程

分两种情况讨论s[i] == ')'：

情况1：s[i-1] == '('→ 形如...()

此时，s[i-1]和s[i]构成一对有效括号。
则dp[i] = dp[i-2] + 2（加上前面的有效长度）。

注意边界：若i < 2，则dp[i-2]视为 0。

情况2：s[i-1] == ')'→ 形如...))

此时，s[i]可能与更早的'('匹配。
设j = i - dp[i-1] - 1，即s[i-1]对应的有效子串前一个字符。

• 若s[j] == '('，则s[j]与s[i]匹配，形成( ... )结构；
• 此时dp[i] = dp[i-1] + 2 + dp[j-1]（中间长度 + 两边长度）。

注意边界：若j < 0或s[j] != '('，则dp[i] = 0。

3.3 初始条件与结果

• 初始化：dp数组全为 0；
• 遍历i从 1 到 n-1（因i=0时若为')'，无法匹配）；
• 最终答案：max(dp[0..n-1])

四、完整答案（方法一：动态规划）

publicclassSolution{publicintlongestValidParentheses(Strings){if(s==null||s.length()<2){return0;}intn=s.length();int[]dp=newint[n];// dp[i]: 以i结尾的最长有效长度intmaxLength=0;for(inti=1;i<n;i++){if(s.charAt(i)==')'){if(s.charAt(i-1)=='('){// 情况1: ...()dp[i]=(i>=2?dp[i-2]:0)+2;}else{// 情况2: ...))intj=i-dp[i-1]-1;// 匹配位置if(j>=0&&s.charAt(j)=='('){dp[i]=dp[i-1]+2+(j>=1?dp[j-1]:0);}// else: dp[i] 保持 0}maxLength=Math.max(maxLength,dp[i]);}// 若 s[i]=='('，dp[i] 保持 0}returnmaxLength;}}

代码说明

• 先处理边界：长度 < 2 时直接返回 0；
• 显式计算j = i - dp[i-1] - 1，逻辑清晰；
• 使用三元运算符处理边界（j-1 < 0时dp[j-1]=0）；
• 实时更新maxLength。

五、代码分析（方法一）

5.1 正确性验证

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

✅maxLength = 4

再看s = "(()"：

✅ 返回 2

5.2 边界处理

• 空字符串：返回 0；
• 单字符：返回 0；
• 全左括号：全 0；
• 全右括号：全 0；
• 有效嵌套：如"((()))"→dp[5]=6。

六、时间复杂度与空间复杂度分析（方法一）

时间复杂度：O(n)

• 单次遍历字符串；
• 每次操作：O(1)（数组访问、比较、加法）；
• 总计：O(n)

空间复杂度：O(n)

• dp数组长度为 n；
• 总计：O(n)

对于n=30000，占用约 120KB 内存（30000 × 4 bytes），完全可接受。

七、答案构思：方法二 —— 栈

7.1 核心思想

利用栈模拟括号匹配过程，记录“最后一个未匹配右括号的位置”作为边界。

关键技巧：初始化栈底为-1，统一处理边界。

7.2 算法流程

1. 初始化栈，压入-1；
2. 遍历字符串：
   • 遇到'('：压入当前索引；
   • 遇到')'：
     • 弹出栈顶（尝试匹配）；
     • 若栈空：说明当前')'无匹配，压入当前索引作为新边界；
     • 否则：当前有效长度 =i - stack.peek()，更新最大值。

7.3 为何栈底是“最后一个未匹配右括号”？

• 栈中存储的是可能作为左边界的位置；
• 当遇到未匹配的')'，它会成为新的左边界（因左边部分已无效）；
• 栈底始终是最近的无效位置，i - stack.peek()即为当前有效长度。

八、完整答案（方法二：栈）

importjava.util.Deque;importjava.util.LinkedList;publicclassSolution{publicintlongestValidParentheses(Strings){Deque<Integer>stack=newLinkedList<>();stack.push(-1);// 初始化边界intmaxLength=0;for(inti=0;i<s.length();i++){if(s.charAt(i)=='('){stack.push(i);}else{stack.pop();// 尝试匹配if(stack.isEmpty()){// 当前 ')' 无匹配，更新边界stack.push(i);}else{// 计算当前有效长度maxLength=Math.max(maxLength,i-stack.peek());}}}returnmaxLength;}}

代码优势

• 逻辑简洁，易于理解；
• 一次遍历，效率高；
• 边界处理优雅（-1初始化）。

九、代码分析（方法二）

9.1 执行过程演示

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

✅ 返回 4

9.2 为何初始化为 -1？

考虑s = "()"：

• i=0: ‘(’ → 栈=[-1,0]
• i=1: ‘)’ → pop → 栈=[-1] → 长度=1 - (-1) = 2 ✅

若不初始化，栈空时无法计算长度。

十、时间复杂度与空间复杂度分析（方法二）

时间复杂度：O(n)

• 单次遍历；
• 每次栈操作：O(1)（均摊）；
• 总计：O(n)

空间复杂度：O(n)

• 栈最坏存储所有'('，即 O(n)；
• 总计：O(n)

与 DP 方法相当，但常数更小（无需数组初始化）。

十一、答案构思：方法三 —— 双指针（O(1) 空间）

11.1 核心思想

贪心统计左右括号数量：

• 从左到右：当right > left时，重置计数器（因多出的')'无法匹配）；
• 从右到左：当left > right时，重置计数器（因多出的'('无法匹配）。

为何需要两次扫描？
因为单向扫描会漏掉left > right始终成立的情况（如"((())"）。

11.2 算法流程

1. 初始化left = right = 0,maxLength = 0；
2. 从左到右遍历：
   • 遇'('：left++
   • 遇')'：right++
   • 若left == right：更新maxLength = max(maxLength, 2*right)
   • 若right > left：重置left = right = 0
3. 从右到左遍历（类似，条件反转）；
4. 返回maxLength

十二、完整答案（方法三：双指针）

publicclassSolution{publicintlongestValidParentheses(Strings){intleft=0,right=0,maxLength=0;intn=s.length();// 从左到右for(inti=0;i<n;i++){if(s.charAt(i)=='('){left++;}else{right++;}if(left==right){maxLength=Math.max(maxLength,2*right);}elseif(right>left){left=right=0;// 重置}}// 从右到左left=right=0;for(inti=n-1;i>=0;i--){if(s.charAt(i)=='('){left++;}else{right++;}if(left==right){maxLength=Math.max(maxLength,2*left);}elseif(left>right){left=right=0;// 重置}}returnmaxLength;}}

代码优势

• 空间复杂度 O(1)；
• 无需额外数据结构；
• 逻辑直观，易于实现。

十三、代码分析（方法三）

13.1 为何需要两次扫描？

反例：s = "((())"

• 左到右：left=3, right=2，始终left>right，不会更新maxLength；
• 右到左：
  • i=4: ‘)’ → right=1
  • i=3: ‘)’ → right=2
  • i=2: ‘(’ → left=1
  • i=1: ‘(’ → left=2 →left==right→maxLength=4✅

13.2 正确性验证

s = ")()())"：

• 左到右：
  • i=0: right=1>left=0 → 重置
  • i=1-2: left=1,right=1 → maxLength=2
  • i=3-4: left=2,right=2 → maxLength=4
• 右到左：
  • i=5: right=1
  • i=4: left=1 → 1!=1? 继续
  • … 最终也会得到 4

✅ 返回 4

十四、时间复杂度与空间复杂度分析（方法三）

时间复杂度：O(n)

• 两次遍历，每次 O(n)；
• 总计：O(n)

空间复杂度：O(1)

• 仅用几个整型变量；
• 总计：O(1)

这是最优空间解法，适合内存受限场景。

十五、常见问题解答（FAQ）

Q1：DP 方法中，为何j = i - dp[i-1] - 1？

A：dp[i-1]是以i-1结尾的有效长度，故有效子串起始位置为i - dp[i-1]。其前一个位置j = i - dp[i-1] - 1就是可能与s[i]匹配的'('。

Q2：栈方法中，为何弹出后栈空要压入当前索引？

A：因为当前')'无匹配，它将成为后续有效子串的左边界（因左边部分已无效）。例如s = ")()"，第一个')'是边界，有效子串从索引 1 开始。

Q3：双指针方法能否只扫描一次？

A：不能。单向扫描无法处理left > right始终成立的情况（如"((())"）。必须正反两次才能覆盖所有情形。

Q4：如果字符串包含其他字符（如[,]），如何扩展？

A：可用栈记录字符类型，或为每种括号维护独立计数器（但双指针法难以扩展，DP 和栈更通用）。

十六、优化思路拓展

16.1 位运算优化（不适用）

本题涉及顺序和匹配，位运算难以建模，故不推荐。

16.2 并行化？

由于依赖前序状态，难以并行。但若只需求近似解，可分段处理后合并（非精确）。

16.3 输出具体子串？

• DP 方法：记录maxLength对应的结束位置，回溯即可；
• 栈方法：记录maxLength时的i和stack.peek()，即为子串[peek+1, i]；
• 双指针：需额外记录起始位置，较复杂。

十七、数据结构与算法基础知识点回顾

17.1 动态规划

• 状态定义是关键：dp[i]表示以i结尾的解；
• 分类讨论：根据s[i-1]的值分情况转移；
• 边界处理：防止数组越界。

17.2 栈的应用

• 匹配问题：括号、HTML标签等；
• 边界记录：通过栈底存储关键位置；
• 单调性：本题中栈存储递增索引。

17.3 双指针与贪心

• 贪心策略：局部最优（重置计数器）导致全局最优；
• 双向扫描：处理不对称问题的标准技巧；
• 空间优化：O(1) 空间的典范。

17.4 字符串处理

• 子串 vs 子序列：本题要求连续；
• 有效性验证：通常用栈或计数器。

十八、面试官提问环节（模拟对话）

面试官：你提到了三种方法，各自优缺点是什么？

答：

• DP：思路清晰，易扩展（如求具体子串），但空间 O(n)；
• 栈：直观模拟匹配，空间 O(n)，但难扩展到多类型括号；
• 双指针：空间 O(1)，效率高，但逻辑稍 tricky，且难扩展。

面试官：栈方法中，为什么初始化为 -1 而不是 0？

答：因为当有效子串从索引 0 开始时（如"()"），长度 =1 - (-1) = 2。若初始化为 0，则1 - 0 = 1，错误。-1作为虚拟左边界，确保计算正确。

面试官：双指针方法的时间复杂度真的是 O(n) 吗？

答：是的。虽然扫描两次，但 2n 仍是 O(n)。常数因子不影响渐进复杂度。

面试官：如果要求最长有效子序列（不要求连续），怎么办？

答：那更简单！只需统计min(count('('), count(')')) * 2即可，因可任意重排。

十九、这道算法题在实际开发中的应用

19.1 编译器与解释器

在语法分析阶段，需检测括号是否匹配。本题的栈方法正是编译器中括号检查的核心逻辑。

19.2 代码编辑器

IDE 的括号高亮、自动补全功能依赖高效的括号匹配算法。最长有效子串可用于提示用户修复范围。

19.3 数据格式验证

JSON、XML 等格式大量使用括号。解析器需快速定位无效区域，本题算法可帮助确定错误位置。

19.4 算法竞赛

括号序列是经典模型，衍生出许多变种（如带权重、多类型），掌握本题是解决更复杂问题的基础。

19.5 生物信息学

DNA/RNA 序列中的碱基配对（如 A-U, G-C）可建模为括号匹配，用于预测二级结构。

二十、相关题目推荐

二十一、总结与延伸

21.1 核心收获

• 动态规划：通过状态定义解决子串问题；
• 栈：天然适合匹配类问题，边界处理是关键；
• 双指针：贪心 + 双向扫描实现 O(1) 空间；
• 问题转化：从“找子串”到“记录边界/状态”。

21.2 延伸思考

• 多类型括号：如{[()]}，需栈存储类型；
• 带权重括号：如"(a)"中a有权重，求最大权重有效子串；
• 在线版本：字符流式到达，需动态维护最长有效长度（可用栈 + 段树）。

21.3 给读者的建议

• 先掌握栈方法，因其最直观；
• 再学 DP，理解状态设计；
• 最后看双指针，体会空间优化之美；
• 面试中可先写栈解法，再提及其他方法展示广度。

结语：最长有效括号是一道集大成的算法题，融合了 DP、栈、双指针三大经典技巧。它不仅是 LeetCode 的热门考题，更是检验算法基本功的试金石。掌握它，你就掌握了处理括号序列问题的通用钥匙。希望本文能助你在技术之路上走得更稳、更远！