LC32　最长有效括号¶

困难通过率 42.5%python3核心代码模式动态规划样例通过牛客 AC栈字符串动态规划括号序列

牛客原题　源码

讲解章节：栈

一句话

用下标栈记住「最后一个没人要的右括号在哪」，栈底垫一个 -1 哨兵。

解题思路¶

这题考什么¶

朴素判定「某个子串是否合法」要 O(n)，枚举全部子串是 O(n 的三次方)， 3e4 的规模下毫无指望。关键在于换一个角度：不去枚举子串，而是把「当前有效段的左边界」一路维护下来。

写法一（本文件采用的下标栈）：栈里存的是下标，不是括号字符。栈底始终是「最后一个无法被匹配的右括号的位置」，它把整个串切成互不相干的段—— 有效子串绝不可能跨过一个多余的右括号。栈里其余元素是尚未配对的左括号的位置。

遇到 '(' -> 下标入栈，等右括号来配
遇到 ')' -> 先弹栈顶
            弹完后栈空 -> 这个右括号没人配，它成为新的分隔点，把 i 压进去
            弹完后非空 -> 配对成功，当前有效段是 (stack[-1], i]，长度 i - stack[-1]

-1 这个哨兵的作用：设想有效段从下标 0 开始（如 "()()"）。配对成功后需要拿「上一个分隔点」来算长度，但此时前面根本没有分隔点。预先在栈底放一个 -1，等价于假想在下标 0 的左边有一个虚拟分隔点，于是 i - stack[-1] 对「从头开始的有效段」也成立，不必单开一条分支。不放哨兵的话，")()())" 这类输入里第一段还能靠真实的分隔点算对，而 "()" 这种从头开始的会因为栈空而算不出长度。

写法二（线性 DP），思路等价，值得对照：

状态定义：f[i] = 以 s[i] 结尾的最长有效括号子串的长度。
转移方程（只有 s[i] == ')' 时才可能非零）：

    s[i-1] == '(' :  f[i] = f[i-2] + 2
    s[i-1] == ')' 且 s[i - f[i-1] - 1] == '(' :
                     f[i] = f[i-1] + 2 + f[i - f[i-1] - 2]

第一条是刚好配上一对；第二条是跨过内层已经合法的一整段 f[i-1]，
去够它左边那个字符，配上之后还要把再往左的 f[...] 接起来。
下标可能为负，每处都要挡边界，比栈版更容易写错，所以本文件选了栈。

数据规模与复杂度¶

0 <= s.length <= 3e4，字符只有 '(' 与 ')'。注意下界是 0—— 题面样例 3 就是空串，期望输出 0。时间 O(n)：每个下标至多入栈一次、出栈一次；空间 O(n)，最坏是全左括号 "(((...("。 3e4 的规模一趟扫描是毫秒级。

坑在哪¶

栈里存下标不是字符。存字符只能判断括号串是否合法，无法算出长度，因为长度需要「当前位置减去段起点」这两个下标。
-1 哨兵不能省。它让「有效段从下标 0 开始」这种情况无需特判，省掉之后 "()" 会在配对时发现栈空而算不出 2。
遇到 ')' 时是先无条件弹栈再看栈空不空，而不是先判空。先判空会把「弹掉的是旧哨兵」和「弹掉的是一个左括号」这两种情形搅在一起。弹完为空说明弹掉的正是旧哨兵，即这个右括号没人配，它自己成为新哨兵。
新哨兵压的是 i（当前右括号的位置），不是 i - 1 或别的值。压错一格，后面所有长度都会差一。
长度算的是 i - stack[-1] 而不是 i - stack[-1] + 1。 stack[-1] 指向的是有效段前面一格（分隔点或未配对的左括号），不属于有效段本身，所以是开区间，差值就是长度。
有效段可以被合并。"(()())" 里内层两对配完后，栈顶回落到最外层的 '(' 之前，一次就算出整段长度 6，不需要显式合并相邻段——这正是用栈的好处。
空串要返回 0。循环一次都不进，best 保持初值 0，天然正确。

样例复核¶

s = ")()())"，起手 stack = [-1]、best = 0。

i=0 ')' : 弹出 -1，栈空 -> 压入 0，stack = [0]
i=1 '(' : 压入 1，stack = [0, 1]
i=2 ')' : 弹出 1，栈非空（栈顶 0）-> best = 2 - 0 = 2
i=3 '(' : 压入 3，stack = [0, 3]
i=4 ')' : 弹出 3，栈顶 0 -> best = 4 - 0 = 4
i=5 ')' : 弹出 0，栈空 -> 压入 5，stack = [5]

返回 4，对应子串 "()()"，与期望输出一致。第 5 步很能说明问题：下标 0 那个多余的右括号一直守在栈底，它左边的内容永远不会被算进右边的有效段。

参考实现¶

solutions/leetcode/LC32/sol.py
from typing import List, Optional


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 栈里存**下标**（存字符只能判合法性，算不出长度）。
        # 栈底是「最后一个无人配对的右括号的位置」，它把串切成互不相干的段；
        # 初值 -1 是哨兵：假想下标 0 的左边有一个虚拟分隔点，
        # 这样「有效段从头开始」也能用同一条公式算长度，不必单开分支
        stack = [-1]
        best = 0
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)             # 左括号一律入栈，等右括号来配
            else:
                # 先无条件弹栈再看空不空：弹掉的要么是一个左括号（配对成功），
                # 要么是旧哨兵（说明这个右括号没人要）。先判空会把两种情形搅在一起
                stack.pop()
                if not stack:
                    # 弹空了 -> 弹掉的是旧哨兵 -> 这个右括号无法配对，它成为新的分隔点。
                    # 压的必须是 i 本身，压错一格后面所有长度都会差一
                    stack.append(i)
                else:
                    # 配对成功。栈顶指向有效段**前面一格**（分隔点或更外层未配对的左括号），
                    # 不属于有效段本身，所以是开区间，长度就是差值而不是差值加一。
                    # 相邻有效段的合并在这里自动完成："(()())" 到 i=5 时栈顶回落到哨兵 -1，
                    # 一次就算出整段长度 6
                    cur = i - stack[-1]
                    if cur > best:
                        best = cur
        return best

LC32 最长有效括号¶