LeetCode 32. 最长有效括号：栈、DP 与一次遍历的三种思路

最长有效括号（LeetCode 32，Hard）是括号匹配的进阶版：普通题问「这个括号串合法吗」（用栈计数即可），这道题问「最长的合法连续子串有多长」。难度跳升的根源在于：合法子串可能出现在任何位置，且「合法」的定义是连续的——中间断一下就要重新数。三种主流解法（栈、DP、双向扫描）看似不同，本质都在回答同一个问题：每个位置 i 结尾的最长有效括号是多少。本篇走完三条路，把它们的共同本质讲透。

解法一：栈——维护「最近未匹配的位置」

栈解法的巧妙改造：普通括号匹配的栈存「未匹配的左括号」，这道题的栈改存下标，并且初始化压入 -1（作为「最近的非法位置」的哨兵）。遍历字符串：遇到 (，下标入栈；遇到 )，先弹栈——弹完若栈空，说明这个 ) 匹配了「非法位置」，它自己成为新的非法位置（当前下标入栈）；弹完若栈非空，当前 ) 与栈顶之间（不含栈顶）就是一段合法子串，长度 = i - stack.top()，更新最大值。为什么这样是对的？栈顶永远维护着「最近的、尚未被合法段覆盖的位置」——两段合法子串之间的非法字符（多出的 ) 或 (）会更新这个哨兵，使得任何时刻 i - stack.top() 恰好是「以 i 结尾的最长合法长度」。代码精炼：

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]                      # 哨兵：最近的非法位置
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:             # 弹空：当前 ) 是新的非法位置
                stack.append(i)
            else:                     # i - 栈顶 = 以 i 结尾的最长合法长度
                best = max(best, i - stack[-1])
    return best

时间空间都是 O(n)。常见坑：忘了哨兵 -1（第一段合法子串的长度算错）、以及「弹空后先入栈再继续」的顺序写反。

解法二：DP——显式定义那个「以 i 结尾」

DP 解法把栈解法隐式维护的东西写成了定义：dp[i] = 以 s[i] 结尾的最长有效括号长度（s[i] 是 ( 时必然为 0，因为有效子串不能以 ( 结尾）。转移分两种情况（s[i] == ')' 时）：情况 A：s[i-1] == '('——形如 ...()，dp[i] = dp[i-2] + 2（前面紧贴的有效段接上）。情况 B：s[i-1] == ')' 且 s[i - dp[i-1] - 1] == '('——形如 ...((...))，dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（内层有效段 + 这对括号 + 更前面紧贴的有效段——第三项最容易漏！它负责把「隔着一对括号的前段」重新接上）。两种情况都要做下标越界检查。答案就是所有 dp[i] 的最大值。DP 与栈的关系：它们计算的是同一个函数（以 i 结尾的最长有效长度），栈是用「哨兵位置」隐式计算，DP 是用「转移方程」显式计算——理解了 DP 的状态定义，栈的每一步都有了对应的语义；面试时先讲 DP（清晰），再讲栈（优雅），是展示思维完整性的好顺序。

解法三：双向扫描——O(1) 空间的一遍半

最省空间的解法是两次线性扫描：维护左右计数器 left/right，正向扫：遇 ( 左计数加一，遇 ) 右计数加一；当 left == right，更新答案 2 * right；当 right > left（非法），双计数清零。问题：正向扫会漏掉「左括号多余」的情形（(() 中 (() 检测不到，因为 right 永远不超过 left）——所以再逆向扫一遍：对称地，当 left > right 清零，left == right 时更新答案。两遍取最大值，覆盖两种「多余方向」，时间 O(n)、空间 O(1)。它的直觉：正向扫保证「右括号不超」（能数出所有以合法段结尾的长度），逆向扫保证「左括号不超」（能数出所有以合法段开头的长度）——两遍合起来，不漏任何一段。三种解法的选用建议：栈最通用（改动少、易扩展），DP 最容易讲清定义（面试表达友好），双向扫描最省空间但边界巧妙（适合作为「还有更优雅解法」的加分展示）。

手动模拟：用「()(」走一遍栈的每一步

用 ()(())（答案 4）完整模拟栈解法，验证每一步的语义。初始栈 [-1]。i=0 '('：下标 0 入栈 → [-1, 0]。i=1 ')'：弹出 0；栈非空（顶为 -1），长度 = 1−(−1) = 2，best=2——"()" 两个字符 ✓。i=2 '('：下标 2 入栈 → [-1, 2]。i=3 '('：下标 3 入栈 → [-1, 2, 3]。i=4 ')'：弹出 3；栈非空（顶为 2），长度 = 4−2 = 2，best 仍 2——"()" ✓（内层括号）。i=5 ')'：弹出 2；栈非空（顶为 -1），长度 = 5−(−1) = 6，best=6——"(()" 加 ")" 组成的 "(())" 加前面的 "()" = "()((…))" 连成 6 长度 ✓。i=5 这一步是本题的精华时刻：它结算的不是「当前括号对」，而是「跨过内层合法段的整段」——哨兵 -1 的价值在此完全显形：它保证了跨段结算时「减法」的基准正确。再模拟一个「断裂」场景确认："())("——i=2 的 ')' 弹出 1 后栈空（弹掉了哨兵），当前下标 2 入栈成为新哨兵——i=3 的 '(' 入栈；结束时 best=2（只有前两位）✓，且新哨兵 2 正确地把后面的 "()" 与前面的合法段隔开。

双向扫描的追问链与流式边界

双向扫描还有一个面试追问链值得准备。第一问「O(n²) 的 DP 会写吗」（验证 DP 基本功）；第二问「空间能优化吗」（引出栈或双向扫描）；第三问「如果只要长度不要位置，空间能到 O(1) 吗」（引出双向扫描）；第四问「如果字符串是流式输入呢」——栈仍然可以（在线算法：边读边维护，读到最后答案即出），双向扫描不行（它需要两端）。一道题的四问，覆盖了从 DP 到栈到流式的完整讨论面；准备面试时，给每道题准备「追问链」比多刷三道新题更有价值。流式边界再补一句：栈解法在流式场景下的语义是「截至当前字符的最长有效后缀」——它的答案会随新字符动态更新，这正是栈作为在线算法的本色。

括号的三兄弟：判断、最长、移除的解法地图

括号家族有三道经典题，解法各成一派，放在一起对比才见全貌。老大：有效括号判断（LeetCode 20）——栈计数器即可（左压右弹，最后栈空即合法）——O(n)/O(n)。老二：最长有效括号（本篇）——栈存下标加哨兵、或 DP、或双向扫描——O(n)/O(n)。老三：移除最少的括号使合法（LeetCode 1249）——需要删除的最少括号数 = 「多余的右括号数 + 多余的左括号数」——一遍扫描计数（右括号超前时记一个待删、扫完后的剩余左括号数再记一批），第二遍按记录删除对应字符——O(n)/O(n)。三兄弟的谱系：老一管「整串合法性」、老二管「局部合法性极值」、老三管「修复的最小代价」——同一套计数器的三种用法：计数器不但能判断，还能定位极值、还能计算修复代价——把一个基础工具的三种用法吃透，胜过背三道题的代码。

三种解法的复杂度对比总表

把三种解法的账本合成一张总表，方便选择。对比的维度：时间（最优/最坏）、空间、实现的出错概率、可扩展性（流式/变体适配）。栈解法：O(n)/O(n)、代码中等复杂、易扩展到「输出具体子串」与「流式」（在线算法）。DP 解法：O(n²)/O(n²)、转移清晰适合讲解、表可复用于「回文计数」等变体。双向扫描：O(n)/O(1)、代码最短、常数最小（两遍线性），但逻辑最巧妙（正向保右不超、逆向保左不超的双保险需要解释成本）。选择建议的决策树：追求空间极致 → 双向扫描；追求讲解清晰 → DP（讲思路）或栈（讲实现）；字符串是流式 → 栈（唯一在线的）；需要输出所有回文子串 → DP 表（信息最全）。总表的最后一行：三种解法的「测试成本」都一样——五个标准用例加对拍，解法可以换，纪律不换。

扩展应用：合法括号串的「结构」用途

「最长有效括号」的思路在工程中还有一个意外应用场景：文本编辑器的括号高亮与错误定位——编辑器实时判断「当前光标处的括号是否匹配」与「最近的有效括号段在哪」，用的正是这套「以每个位置结尾的最长合法长度」的逻辑——编辑器把每一步的栈状态可视化（未匹配的左括号高亮），配合本篇的算法，用户的括号错误能被精确地提示到字符级。延伸到代码 lint 工具：括号的「最长合法段」信息还可以驱动「格式化建议」（合法段的缩进校正）与「重构辅助」（合法段的整段选中与重排）。这类应用的共同点：算法的输出（每个位置的最长合法长度）不是最终产品，是编辑器交互的中间信号——算法题的工程化，常常就是把「答案」重新定位成「信号」。

DP 解法的细节与「填表顺序」的直觉

DP 解法的状态转移 dp[i][j] 依赖「更短的子串」——填表顺序必须按子串长度从短到长（长度 1 → 长度 2 → …），而不是按 i、j 的字典序——按字典序填表时 dp[i+1][j-1]（更短的对角线）可能还没算好，转移就会读到未定义值。填表顺序的确定方法：看转移依赖的「方向」——本体的依赖是「左下方向」（长度更短的子串），所以按长度遍历；本库《编辑距离》的依赖是「上、左、左上」，按行遍历即可——依赖方向决定遍历顺序，是所有二维 DP 的通用纪律。DP 解法还有一个工程细节：dp 表的维度是 (n+1)×(n+1) 还是 n×n——用 (n+1) 的「哨兵版」（空串的边界自然是 0）比 n×n 加特判的写法更不易错——哨兵化是 DP 代码可靠性的通用技巧（边界自然融入主体循环，无特判分支）。

小结

这篇收成四条：栈解法的灵魂是哨兵——栈顶维护「最近的非法位置」，i - 栈顶 即以 i 结尾的最长合法长度；DP 解法显式定义 dp[i] 为「以 i 结尾的最长有效长度」，情况 B 的第三项（隔对括号的前段）最容易漏；双向扫描用两次 O(n) 换 O(1) 空间，正向保「右不超」、逆向保「左不超」；三种解法的共同本质是同一个状态——「以每个位置结尾的最长合法括号」——不同只是隐式还是显式地维护它。括号三部曲（合法判断 → 最长有效 → 生成所有合法组合《括号生成》）至此凑齐两篇，回溯的那一篇见本系列《括号生成》。

参考资料

• LeetCode 32. Longest Valid Parentheses —— 题目与官方题解（三种解法均有）
• 本库前篇：《LeetCode 84. 柱状图中最大的矩形：单调栈的直觉与证明》《LeetCode 22. 括号生成》