LeetCode 32 最长有效括号：python3 题解

题目链接：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 结尾的最长有效括号子串的长度。
状态转移：

• 如果 s == '('：dp = 0（有效括号不可能以左括号结尾）。
  
• 如果 s == ')'：
  
  
  
  • 情况 A：s[i-1] == '('。形成了 "(...())" 结构。
    
    
    
    • dp = 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 = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（加上再前面的有效长度）。
      
    
    
  
  

优点： 标准的 DP 思路，适合练习动态规划。
缺点： 状态转移方程较复杂，容易写错边界条件。
解法三：双指针（两次遍历）—— 空间最优

核心思想：
利用计数器 left 和 right。

• 从左到右遍历：
  
  
  
  • 遇到 '('，left++；遇到 ')'，right++。
    
  • 如果 left == right，说明找到一段有效括号，长度 2 * right。
    
  • 如果 right > left，说明右括号多了，前面的都无效了，重置 left = right = 0。
    
  • 缺陷：无法处理 "(()" 这种情况（遍历结束 left > right，不会更新最大值）。
    
  
  
• 从右到左遍历：
  
  
  
  • 逻辑同上，但重置条件变为 left > right。
    
  • 这样可以处理 "(()" 这种情况。
    
  
  

优点： 空间复杂度 \(O(1)\)，不需要额外数组或栈。
缺点： 需要遍历两次，且逻辑需要理解为什么需要两次。
3. 代码实现

下面提供三种解法的完整代码。
栈解法

1. class Solution:
2.     def longestValidParentheses(self, s: str) -> int:
3.         # 初始化最大长度
4.         max_len = 0
5.         # 初始化栈，放入 -1 作为基准点
6.         # 基准点的作用是：当有效括号从索引 0 开始时，方便计算长度
7.         stack = [-1]
8.         
9.         # 遍历字符串的每个字符及其索引
10.         for i, char in enumerate(s):
11.             if char == '(':
12.                 # 遇到左括号，将索引压入栈，等待匹配
13.                 stack.append(i)
14.             else:
15.                 # 遇到右括号
16.                 # 弹出栈顶元素，表示匹配了一个左括号或基准点
17.                 stack.pop()
18.                
19.                 if not stack:
20.                     # 如果栈空了，说明当前的右括号没有左括号可以匹配
21.                     # 它成为了新的“无效边界”，将当前索引压入栈作为新的基准
22.                     stack.append(i)
23.                 else:
24.                     # 如果栈不为空，说明匹配成功
25.                     # 当前有效长度 = 当前索引 - 栈顶索引（栈顶是上一个无效位置）
26.                     current_len = i - stack[-1]
27.                     # 更新最大长度
28.                     max_len = max(max_len, current_len)
29.                     
30.         return max_len

复制代码

动态规划解法

1. class SolutionDP:
2.     def longestValidParentheses(self, s: str) -> int:
3.         if not s:
4.             return 0
5.         
6.         n = len(s)
7.         # dp[i] 表示以 i 结尾的最长有效括号长度
8.         dp = [0] * n
9.         max_len = 0
10.         
11.         for i in range(1, n):
12.             if s[i] == ')':
13.                 # 情况 1: ...()
14.                 if s[i-1] == '(':
15.                     dp[i] = (dp[i-2] if i >= 2 else 0) + 2
16.                 # 情况 2: ...))
17.                 # 需要检查前面的有效括号之前是否是 '('
18.                 elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
19.                     # 当前匹配长度 + 2 + 再前面的有效长度
20.                     dp[i] = dp[i-1] + 2 + (dp[i - dp[i-1] - 2] if i - dp[i-1] >= 2 else 0)
21.                
22.                 max_len = max(max_len, dp[i])
23.                
24.         return max_len

复制代码

双指针解法 - 空间 O(1)

1. class SolutionTwoPass:
2.     def longestValidParentheses(self, s: str) -> int:
3.         max_len = 0
4.         left = 0
5.         right = 0
6.         
7.         # 第一次遍历：从左到右
8.         for char in s:
9.             if char == '(':
10.                 left += 1
11.             else:
12.                 right += 1
13.             
14.             if left == right:
15.                 # 左右平衡，找到有效子串
16.                 max_len = max(max_len, 2 * right)
17.             elif right > left:
18.                 # 右括号多了，无效，重置
19.                 left = right = 0
20.         
21.         # 重置计数器
22.         left = right = 0
23.         
24.         # 第二次遍历：从右到左
25.         # 为了处理 "(()" 这种左括号多于右括号的情况
26.         for char in reversed(s):
27.             if char == '(':
28.                 left += 1
29.             else:
30.                 right += 1
31.             
32.             if left == right:
33.                 max_len = max(max_len, 2 * left)
34.             elif left > right:
35.                 # 左括号多了，无效，重置
36.                 left = right = 0
37.                
38.         return max_len

复制代码

4. 复杂度分析

解法时间复杂度空间复杂度评价栈 (Stack)\(O(n)\)\(O(n)\)最推荐。逻辑清晰，代码简洁，不易出错。动态规划 (DP)\(O(n)\)\(O(n)\)适合 DP 练习，但状态转移方程较难推导。双指针 (Two Pass)\(O(n)\)\(O(1)\)空间最优，但需要遍历两次，且逻辑需小心处理边界。

• \(n\) 是字符串 s 的长度。
  
• 题目限制 \(n \le 3 \times 10^4\)，三种 \(O(n)\) 解法均可通过。
  

5. 总结与建议

• 首选栈解法：在面试中，栈解法最容易向面试官解释清楚。它直接模拟了括号匹配的过程。
  
• 注意基准点：栈初始化放入 -1 是这道题的精髓，避免了单独处理从索引 0 开始的有效子串。
  
• 边界条件：注意空字符串 "" 的处理（代码中循环不会执行，直接返回 0，逻辑自然成立）。
  
• 空间优化：如果对空间要求极高（如嵌入式环境），可以使用双指针解法。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！