最长有效括号

枚举所有子串是 O(n 平方) 个，每个再扫一遍判断合法是 O(n)，合起来 O(n 的三次方)。字符串长度到 3 万时直接超时。

遇到 "(" 就压入它的下标；遇到 ")" 先弹一个。弹完后栈空，说明这个 ")" 是新的非法边界；栈不空，当前合法长度就是 i 减去栈顶下标。

一开始先压一个哨兵 −1，代表字符串开始前的边界。这样从下标 0 开始的合法串，也能用 i 减栈顶算出长度。

初始化：先放哨兵 −1：我们用例子 ")()())" 来演。先把哨兵 −1 压进栈，它代表「开头之前」这条看不见的左墙。

i=0 读到 ")"：先弹一次：开头就是右括号，肯定配不上谁。代码统一处理：遇到 ")" 一律先 pop。这一弹，连哨兵 −1 都被弹掉了，栈空了。

栈空：下标 0 变成新边界：弹完栈空，说明这个 ")" 没配上。把它自己的下标 0 压回去，当新的左墙——后面的合法段都不许跨过它。

i=1 读到 "("：压入下标：左括号还没被匹配，把它的下标 1 压栈。栈底那个 0 仍然是不能跨过的边界。

i=2 读到 ")"：弹出匹配的 "("：这个右括号配上了下标 1 的左括号，弹掉它。弹完后栈顶露出 0，它就是当前合法段左边的边界。

栈不空：用 i − 栈顶 更新答案：栈不空，关键的一步来了：长度不是「刚才那一对」，而是 i 减栈顶。以下标 2 结尾的合法段是 1..2，长度 2。

i=3 读到 "("：继续压入：又一个左括号，压入下标 3。它可能跟后面的右括号组成新的一对，也可能跟前面的合法段连起来。

i=4 读到 ")"：弹出下标 3：下标 3 和 4 配成一对，弹掉 3。重点：别只盯这一对，弹完后看栈顶是谁，决定它能不能跟前面连上。

连续合法段一口气扩到长度 4：栈顶还是 0，说明从下标 1 到 4 中间没被任何非法右括号切断。所以这段是 "()()"，长度 4 — 这正是「存下标」的威力。

i=5 读到 ")"：再弹一次：最后一个右括号没有对应的左括号。弹掉栈顶 0 后栈空，说明它要成为新的非法边界。

栈空：下标 5 成新边界，答案不变：非法右括号只负责切断后面的连续段，它自己不更新答案。当前最好成绩仍是前面算出的 4。

扫描结束：返回 ans：整串扫完，ans 里存的就是最长有效括号子串长度。对 ")()())" 答案是 4。

灵魂帧慢放：再看一眼「弹完后看栈顶」：把整题压成一句话：右括号先弹，弹完看栈顶。栈空就把自己当新墙；栈不空，i 减栈顶就是以 i 结尾的最长合法段。这一步是全题唯一的命门，记住它就够了。

一旦答案跟距离、长度、区间有关，栈里往往该存下标而不是值——这是括号长度题最值钱的一句迁移点。

雷区实演：用「i − 被弹下标」会错成 2：在 i=4 这一步，如果用「i 减刚弹掉的下标 3」，只会得到这一对的长度，把前面连着的 "()" 漏掉，答案被压成更小的值。必须用弹完后的栈顶 0，才能把相邻合法段接上得到 4。

边界三连：最容易翻车的不是空串，而是「中间断一刀」的串：要确认非法边界真的把两段切开了，没被错误地连成一长段。

面试追问：栈解最直观，但面试官常追问「O(1) 双向扫」和「DP 状态定义」——这两个备解能拉开档次。

先吃透 20 题括号匹配（存字符），再到 32 题最长有效（存下标），就能迁移到 84 柱状图最大矩形、739 每日温度这类「栈存下标算距离」的题。想系统练可以点右侧的栈专题，或问问 AI 助教「下标栈还能解哪些题」。