最长有效括号子串

题目

最长有效括号子串

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

动态规划, 栈操作, 边界条件处理, 字符串遍历优化

快速回答

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

核心解法：

• 动态规划：定义 dp[i] 表示以 s[i] 结尾的最长有效括号长度
• 栈辅助：利用栈存储未匹配括号的索引，实时计算长度
• 关键方程：当 s[i]=')' 且 s[i-1]='(' 时，dp[i] = dp[i-2] + 2；当 s[i]=')' 且 s[i-1]=')' 时需二次判断

时间复杂度 O(n)，空间复杂度 O(n)

解析

问题描述

给定仅包含 '(' 和 ')' 的字符串，如 "()(())" 或 ")(()()){"，求最长连续有效括号子串的长度。有效指括号正确匹配，如 "()(()){" 的最长有效子串为 "()(())" 长度=6。

原理说明

动态规划核心逻辑：

• 定义 dp[i] 表示以字符 s[i] 结尾的最长有效括号长度
• 初始化：dp[0]=0（单个字符无效）
• 状态转移：
  1. 当 s[i] = ')' 且 s[i-1] = '(' 时：
     dp[i] = dp[i-2] + 2
  2. 当 s[i] = ')' 且 s[i-1] = ')' 时：
     若 s[i - dp[i-1] - 1] = '('，则：
     dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]

栈解法原理：

• 栈底始终存储「最后一个未被匹配的')'的索引」
• 遇到 '(' 时压栈其索引
• 遇到 ')' 时：
  1. 弹出栈顶（匹配成功）
  2. 若栈空：当前索引入栈（作为新基准）
  3. 栈非空：当前索引减栈顶索引即为有效长度

代码示例

动态规划实现：

def longestValidParentheses(s: str) -> int:
    n = len(s)
    if n < 2: return 0
    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] == '(':
                prev = dp[i - dp[i-1] - 2] if (i - dp[i-1]) >= 2 else 0
                dp[i] = dp[i-1] + prev + 2
            max_len = max(max_len, dp[i])
    return max_len

栈实现：

def longestValidParentheses(s: str) -> int:
    stack = [-1]  # 哨兵节点
    max_len = 0
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # 更新基准
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

最佳实践

• 首选动态规划：逻辑清晰，性能稳定（O(n)时间/空间）
• 栈方案优势：代码更简洁，适合流式处理
• 空间优化：双向扫描法（O(1)空间）可替代：
  • 从左到右统计 '(' 和 ')' 数量
  • 当右括号多时重置计数器
  • 反向再扫描一次处理左括号多的情况

常见错误

• 边界处理缺失：未处理 i-2<0 的越界情况
• 状态转移遗漏：嵌套场景未累加前序有效长度（如 dp[i - dp[i-1] - 2]）
• 栈初始化错误：未设置栈底哨兵（-1）导致空栈 pop 异常
• 连续匹配中断：未考虑 "()(()" 中最后两个字符实际可连接前段

扩展知识

• 多括号类型扩展：若包含 {}、[]，需增加栈中括号类型匹配检查
• 变体问题：求所有最长有效子串（而不仅是长度），需记录所有满足 max_len 的区间
• 实时处理优化：流式场景下，栈方案可逐字符处理，动态规划需缓存整个 dp 数组
• 理论边界：该问题存在 O(n)/O(1) 的最优解（双向扫描），但代码可读性较低