BM77　最长的括号子串¶

较难通过率 25.51%python3核心代码模式样例通过牛客 AC字符串栈动态规划

牛客原题　源码

讲解章节：栈

一句话

栈里存下标，栈底垫一个「上一个中断位置」，配对时用下标差取长度。

解题思路¶

这题考什么¶

合法括号子串一定是「若干次成功配对连成的一片连续区间」，所以真正要找的不是配对数量，而是每段连续合法区间的左边界。栈的一般用法见栈。

栈里存的是下标而不是字符，并预先压入 -1 当哨兵，它的含义始终是「最近一个使匹配中断的位置」：

遇到 '('：把它的下标压栈，等待将来被某个 ')' 配掉
遇到 ')'：先弹栈

    - 弹完栈空了：这个 ')' 没人配得上，它自己成为新的中断点，压入它的下标
    - 弹完栈非空：栈顶就是当前合法段左边界的**前一格**，
      本段长度 = i - stack[-1]，用它更新答案

循环不变量是「栈顶永远是当前这段合法区间左边界的前一个位置」，所以下标一减就是长度，不需要额外记录段起点，也天然把相邻的两段合并了。

等价的 DP 写法（dp[i] = 以下标 i 结尾的最长合法长度）：

s[i] == ')' 且 s[i-1] == '(' ：  dp[i] = dp[i-2] + 2
s[i] == ')' 且 s[i-1] == ')' ：
    设 k = i - dp[i-1] - 1（与 s[i] 配对的候选左括号位置）
    若 k >= 0 且 s[k] == '(' ： dp[i] = dp[i-1] + 2 + dp[k-1]

两者同为 O(n)；栈写法的边界判断少、常数更小，n 达到 5e5 时更稳。

数据规模与复杂度¶

0 <= n <= 5e5，时限 2 秒（其他语言）。单趟扫描，每个字符至多入栈出栈各一次，时间 O(n)、空间 O(n)（最坏是全 '(' 的串），与题面要求一致。5e5 次 Python 级迭代，循环体只有几条判断，余量充足。

坑在哪¶

栈里存下标而不是字符。只压 '(' 这个字符就只能数出配对总数，而题目要的是连续区间："()(()" 有 2 对配对共 4 个字符，最长的连续合法子串却是 "()"，长度只有 2。两者不是一回事。
栈底的 -1 哨兵不能省。没有它，第一段以下标 0 开头的合法串会在弹栈后遇到空栈，长度就算不出来；-1 的语义是「下标 0 之前那个虚拟的中断点」。
弹空之后压入的是当前这个右括号的下标 i，不是 i+1 也不是别的值：它就是新的中断点，下一段合法区间只能从 i+1 起。
长度是 i - stack[-1]，不是 i - stack[-1] + 1。栈顶指向的是左边界的前一格，本来就不属于这一段。
无条件先 pop 再判空是这段代码的写法要点：')' 无论配得上配不上都要先弹一次，区别只在弹完之后栈是否为空。先判空再决定是否弹会多出两条分支。

样例复核¶

")()())"：i = 0 弹空后压入 0；i = 2 配对，长度 2 - 0 = 2； i = 4 配对，长度 4 - 0 = 4；i = 5 弹空后压入 5。答案 4，与期望输出一致。

参考实现¶

solutions/nowcoder/BM77/sol.py
from typing import List, Optional


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        best = 0
        # 栈里存**下标**；栈底垫 -1 表示「下标 0 之前那个虚拟的中断点」，
        # 循环不变量：栈顶始终是当前合法区间左边界的前一格
        stack = [-1]
        for i, ch in enumerate(s):
            if ch == "(":
                stack.append(i)         # 左括号先记下位置，等待将来被配掉
            else:
                stack.pop()             # 右括号无论配得上与否都先弹一次，再看栈空不空
                if not stack:
                    stack.append(i)     # 弹空说明这个 ')' 多余，它自己成为新的中断点
                else:
                    # 栈顶是左边界的前一格，所以长度直接是下标差，不用加一
                    length = i - stack[-1]
                    if length > best:
                        best = length
        return best

BM77 最长的括号子串¶