当前位置：首页 > news >正文

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

news 2026/7/1 2:14:53

1. 题目解读

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

什么是“格式正确”？

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

关键点：

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

示例分析：

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

2. 解题思路讨论

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

解法一：栈 (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

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

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

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

状态转移：

如果s[i] == '('：dp[i] = 0（有效括号不可能以左括号结尾）。
如果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。

从左到右遍历：
- 遇到'('，left++；遇到')'，right++。
- 如果left == right，说明找到一段有效括号，长度2 * right。
- 如果right > left，说明右括号多了，前面的都无效了，重置left = right = 0。
- 缺陷：无法处理"(()"这种情况（遍历结束left > right，不会更新最大值）。
从右到左遍历：
- 逻辑同上，但重置条件变为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)	空间最优，但需要遍历两次，且逻辑需小心处理边界。