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

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 0i0,s[0]): pop(-1) - stack 空。push(0)。stack [0]i1,s[1](: push(1)。stack [0, 1]i2,s[2]): pop(1) - stack[0]。不为空。len 2 - 0 2。max_len 2i3,s[3](: push(3)。stack [0, 3]i4,s[4]): pop(3) - stack[0]。不为空。len 4 - 0 4。max_len 4i5,s[5]): pop(0) - stack 空。push(5)。stack [5]结果4优点逻辑直观符合括号匹配的直觉。缺点需要 () 的额外空间。解法二动态规划 (Dynamic Programming)核心思想定义dp[i]为以索引i结尾的最长有效括号子串的长度。状态转移如果s[i] (dp[i] 0有效括号不可能以左括号结尾。如果s[i] )情况 As[i-1] (。形成了(...())结构。dp[i] dp[i-2] 2如果i2否则就是 2。情况 Bs[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 0n len(s)# dp[i] 表示以 i 结尾的最长有效括号长度dp [0] * nmax_len 0for 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 0left 0right 0# 第一次遍历从左到右for char in s:if char (:left 1else:right 1if 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 1else:right 1if left right:max_len max(max_len, 2 * left)elif left right:# 左括号多了无效重置left right 0return max_len4. 复杂度分析解法时间复杂度空间复杂度评价栈 (Stack)()()最推荐。逻辑清晰代码简洁不易出错。动态规划 (DP)()()适合 DP 练习但状态转移方程较难推导。双指针 (Two Pass)()(1)空间最优但需要遍历两次且逻辑需小心处理边界。 是字符串s的长度。题目限制 ≤3×104三种 () 解法均可通过。5. 总结与建议首选栈解法在面试中栈解法最容易向面试官解释清楚。它直接模拟了括号匹配的过程。注意基准点栈初始化放入-1是这道题的精髓避免了单独处理从索引 0 开始的有效子串。边界条件注意空字符串的处理代码中循环不会执行直接返回 0逻辑自然成立。空间优化如果对空间要求极高如嵌入式环境可以使用双指针解法。