首页/资讯中心/详情

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

LeetCode 32 最长有效括号：python3 题解
📅 发布时间：2026/7/1 2:14:53

1. 题目解读

题目含义：
给定一个只包含'('和')'的字符串，我们需要找到其中最长的、连续的、且格式正确的括号子串的长度。

什么是“格式正确”？

  1. 左括号'('必须有对应的右括号')'闭合。
  2. 括号必须成对出现，且嵌套顺序正确。
    • 正确示例："()","(())","()()","(()())"
    • 错误示例："(",")","(()",")("

关键点：

  • 必须是子串（连续的一段），不能是子序列（挑着选）。
  • 我们需要返回的是长度，而不是子串本身。

示例分析：

  • 输入："(()"
    • 索引 0,1 是"()"(有效，长度 2)
    • 索引 0,1,2 是"(()"(无效)
    • 最长有效长度是 2。
  • 输入：")()())"
    • 索引 1,2 是"()"
    • 索引 1,2,3,4 是"()()"(有效，长度 4)
    • 最长有效长度是 4。

2. 解题思路讨论

这道题是经典的字符串处理问题，主要有三种主流解法：栈（Stack）、动态规划（DP）和双指针（两次遍历）。它们的时间复杂度都是 �(�)，但空间复杂度和思维难度不同。

解法一：栈 (Stack) —— 最直观

核心思想：
利用栈来跟踪括号的下标。栈底始终保存“最后一个无法匹配的右括号的索引”或者“初始基准点”。

具体步骤：

  1. 初始化一个栈，放入-1。
    • 为什么放 -1？这是一个基准点。如果有效括号从字符串索引 0 开始（例如"()"），计算长度时需要用当前索引 - 栈顶索引。如果栈顶是 -1，长度就是1 - (-1) = 2，计算正确。
  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

优点：逻辑直观，符合括号匹配的直觉。
缺点：需要 �(�) 的额外空间。

解法二：动态规划 (Dynamic Programming)

核心思想：
定义dp[i]为以索引i结尾的最长有效括号子串的长度。

状态转移：

  1. 如果s[i] == '('：dp[i] = 0（有效括号不可能以左括号结尾）。
  2. 如果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 思路，适合练习动态规划。
缺点：状态转移方程较复杂，容易写错边界条件。

解法三：双指针（两次遍历）—— 空间最优

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

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

优点：空间复杂度 �(1)，不需要额外数组或栈。
缺点：需要遍历两次，且逻辑需要理解为什么需要两次。

3. 代码实现

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

栈解法

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

动态规划解法

class SolutionDP:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
n = len(s)
# dp[i] 表示以 i 结尾的最长有效括号长度
dp = [0] * n
max_len = 0
for i in range(1, n):
if s[i] == ')':
# 情况 1: ...()
if s[i-1] == '(':
dp[i] = (dp[i-2] if i >= 2 else 0) + 2
# 情况 2: ...))
# 需要检查前面的有效括号之前是否是 '('
elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
# 当前匹配长度 + 2 + 再前面的有效长度
dp[i] = dp[i-1] + 2 + (dp[i - dp[i-1] - 2] if i - dp[i-1] >= 2 else 0)
max_len = max(max_len, dp[i])
return max_len

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

class SolutionTwoPass:
def longestValidParentheses(self, s: str) -> int:
max_len = 0
left = 0
right = 0
# 第一次遍历：从左到右
for char in s:
if char == '(':
left += 1
else:
right += 1
if left == right:
# 左右平衡，找到有效子串
max_len = max(max_len, 2 * right)
elif right > left:
# 右括号多了，无效，重置
left = right = 0
# 重置计数器
left = right = 0
# 第二次遍历：从右到左
# 为了处理 "(()" 这种左括号多于右括号的情况
for char in reversed(s):
if char == '(':
left += 1
else:
right += 1
if left == right:
max_len = max(max_len, 2 * left)
elif left > right:
# 左括号多了，无效，重置
left = right = 0
return max_len

4. 复杂度分析

解法时间复杂度空间复杂度评价
栈 (Stack)�(�)�(�)最推荐。逻辑清晰，代码简洁，不易出错。
动态规划 (DP)�(�)�(�)适合 DP 练习，但状态转移方程较难推导。
双指针 (Two Pass)�(�)�(1)空间最优，但需要遍历两次，且逻辑需小心处理边界。
  • � 是字符串s的长度。
  • 题目限制 �≤3×104，三种 �(�) 解法均可通过。

5. 总结与建议

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