跳到主要内容

0032. 最长有效括号

题目描述​

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

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

解题思路​

第一步：理解问题本质​

有效括号子串要求连续且完全匹配。比如 "()()" 长度为 4，"(())" 长度也为 4，但 "()(())" 中间有一个嵌套，整体长度为 6。

难点在于：有效括号可以嵌套，也可以连续拼接，还可能被一个多余的 ')' 打断。我们需要找的是其中最长的一段。

第二步：暴力解法​

枚举所有起点和终点，逐一判断子串是否是有效括号。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        def is_valid(sub: str) -> bool:
            count = 0
            for c in sub:
                if c == '(':
                    count += 1
                else:
                    count -= 1
                    if count < 0:
                        return False
            return count == 0

        n = len(s)
        res = 0
        for i in range(n):
            for j in range(i + 2, n + 1, 2):  # 有效括号长度必须为偶数
                if is_valid(s[i:j]):
                    res = max(res, j - i)
        return res

为什么不够好：

  • 枚举起终点需要 O(n²) 对，每次验证需要 O(n)，总体时间复杂度 O(n³)。
  • 对于长度 10000 的字符串，约需 10¹² 次操作，远超时间限制。

第三步：优化解法——动态规划​

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

为什么只看"以 s[i] 结尾"：有效括号必然以 ')' 结尾，所以 s[i] == '(' 时 dp[i] = 0。对于 s[i] == ')'，分两种情况：

情况一：s[i-1] == '('，即 s[i-1] 和 s[i] 直接配对。

... [ dp[i-2] 长的有效串 ] ( )
                             i-1 i

此时：dp[i] = dp[i-2] + 2（把前面已有的有效串加上这对括号）

情况二：s[i-1] == ')'，即 s[i-1] 已经是某个有效串的结尾。

... ( [ dp[i-1] 长的有效串 ] )
  k                           i

令 k = i - dp[i-1] - 1，即 s[i] 对应的左括号候选位置。若 s[k] == '('，则：

dp[i] = dp[i-1] + 2 + dp[k-1]

其中 dp[k-1] 是 k 左边紧邻的有效串长度（两段有效串可以拼接）。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        dp = [0] * n
        res = 0
        for i in range(1, n):
            if s[i] == ')':
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                elif dp[i - 1] > 0:
                    k = i - dp[i - 1] - 1
                    if k >= 0 and s[k] == '(':
                        dp[i] = dp[i - 1] + 2 + (dp[k - 1] if k >= 1 else 0)
                res = max(res, dp[i])
        return res

时间 O(n)，空间 O(n)。

第四步：最优解法——栈（最简洁）​

核心思想：用栈存储字符的下标，用一个哨兵 -1 作为计算有效长度的基准。

为什么要存下标而不是字符：知道下标才能计算区间长度（i - stack[-1]）。

哨兵的作用：当栈只剩哨兵时，说明当前 ')' 没有可以匹配的 '('，这个 ')' 将成为新的"分界线"，更新为新的基准。

完整逻辑：

  • 初始化栈为 [-1]（哨兵）。
  • 遇到 '('：将其下标压栈。
  • 遇到 ')'：弹出栈顶。
    • 若栈变为空：当前 ')' 无法匹配，将其下标压栈作为新哨兵。
    • 若栈非空：有效括号区间为从栈顶下标到当前下标，长度为 i - stack[-1]。

完整代码实现​

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0

        res = 0
        stack = [-1]  # 哨兵：作为计算长度的基准

        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)   # 左括号：记录下标
            else:
                stack.pop()       # 右括号：弹出栈顶（尝试匹配）
                if not stack:
                    stack.append(i)  # 无法匹配，此 ')' 成为新基准
                else:
                    res = max(res, i - stack[-1])  # 当前有效串长度

        return res

示例推演​

以 s = ")()())" 为例，逐步演示：

初始状态：stack = [-1]，res = 0

is[i]操作stack 状态res
0)弹出 -1，栈空，将 0 压入作为新哨兵[0]0
1(将 1 压入[0, 1]0
2)弹出 1，栈非空（顶为 0），长度 = 2-0 = 2[0]2
3(将 3 压入[0, 3]2
4)弹出 3，栈非空（顶为 0），长度 = 4-0 = 4[0]4
5)弹出 0，栈空，将 5 压入作为新哨兵[5]4

最终结果：res = 4，对应子串 "()()" （下标 1 到 4）。

再看嵌套情况：s = "(()"

初始：stack = [-1]，res = 0

is[i]操作stackres
0(压入 0[-1, 0]0
1(压入 1[-1, 0, 1]0
2)弹出 1，栈非空（顶为 0），长度 = 2-0 = 2[-1, 0]2

最终结果：res = 2，对应子串 "()" （下标 1 到 2）。

复杂度分析​

解法时间复杂度空间复杂度说明
暴力枚举O(n³)O(n)枚举所有子串，逐一验证
动态规划O(n)O(n)一次遍历，dp 数组存储中间结果
栈（最优）O(n)O(n)一次遍历，栈最多存 n 个下标

动态规划和栈在时间复杂度上相同，但栈的代码更简洁，逻辑更直观。

易错点总结​

  • 哨兵不能省略：如果没有初始的 -1，第一对有效括号的长度无法正确计算（i - stack[-1] 会取到栈中最近的左括号下标，而非基准下标）。

  • 弹出后判断栈是否为空：弹出操作之后，必须先检查栈是否为空，再决定是更新结果还是压入新哨兵。如果顺序弄反，会导致数组越界或逻辑错误。

  • 动态规划中的 dp[k-1] 拼接：两段有效括号可以连续，第二段左边的 dp[k-1] 代表第一段的长度，不能漏加。

  • 下标越界保护：在动态规划中，访问 dp[i-2] 和 dp[k-1] 时需要检查下标是否 >= 0。

扩展思考​

  • LeetCode 20. 有效的括号：判断单个字符串是否是有效括号，是本题的基础。

  • LeetCode 301. 删除无效的括号：找到所有删除最少括号后得到的有效括号字符串，难度更高，需要 BFS。

  • 算法本质：栈天然适合处理括号匹配类问题，因为括号的"最近未匹配"特性与栈的后进先出完美契合。用下标代替字符入栈是解决"长度计算"类问题的通用技巧。

加载评论中...