题目描述
思路解析
一句话答案：LeetCode 32 最长有效括号的经典解法是栈里存下标：先压入 -1 当边界哨兵，遇左括号压下标，遇右括号先弹栈——弹后栈非空就用 i 减新栈顶得到以 i 结尾的有效段长度，弹空则说明这个右括号是断点、把 i 压入当新边界。一次遍历，时间 O(n)、空间 O(n)。
最长有效括号这道题在问什么
在一个只含左右括号的串里，找最长的一段连续子串，使它是完全合法、能全部配对的括号串。注意两点：一是要求连续子串而不是子序列，中间一个落单的右括号就会把有效段拦腰切断；二是答案只要长度这个数字，不用输出子串本身。
会判合法为什么还不够，栈里为什么存下标
用栈判断括号串是否合法是基本功：左括号进栈，右括号消掉一个栈顶。但本题要的是长度，只知道「配上了」远远不够，还得知道这一段合法串从哪里开始。这逼出关键的一步改造：栈里不存括号字符，改存下标。位置信息进了栈，长度才有得算——某段合法串的长度，就是它右端点减去左端点前面那个位置。
于是问题聚焦成一件事：扫到位置 i 收获一个配对时，怎么快速知道「以 i 结尾的有效段」左端在哪。答案藏在栈的形态里。
栈底为什么始终是当前段左边界的前一位
算法维持这样一条不变量：栈底永远存着「当前有效段左边界的前一个下标」，栈里其余元素是还没配对的左括号下标。开局先压 -1，代表最初的有效段可以从下标 0 起步。扫描规则：遇左括号压 i 占位；遇右括号先弹一个——若弹后栈非空，说明配对成功，i - stack[-1] 就是以 i 结尾的最长有效长度，拿去刷新最大值；若弹空了，说明这个右括号没有搭档，它是新的断点，把 i 压入接任边界。
断点接任边界这步是灵魂：后面的有效段无论多长都跨不过这个孤儿右括号，所以从它之后重新起算，正好由「i 减栈底」自动兑现。
相邻有效段的拼接为什么自动发生
很多人担心 ()(()) 这种「两段挨着」的情形要不要特判，其实不用。以串 ()(()) 为例：扫到最后一个右括号时，中间所有配对的下标都已被成双弹掉，栈里只剩最初的 -1，i - (-1) = 6 一次量出整段长度。原因在于：只要两段之间没有断点，中间的下标就不会滞留在栈里，i 减栈顶天然跨过所有已配对的部分，合并不需要任何额外逻辑。
复杂度与常见翻车点
时间 O(n)，每个字符至多进出栈一次；空间 O(n)，最坏全是左括号全部压栈。三个高频错误：忘了先压 -1，第一段合法串的长度就量不出来；右括号弹空后忘记把 i 压回去，断点丢失、后面全部算错；以及栈里存字符而不是下标，长度无从谈起。若追求 O(1) 空间，还有左右各扫一遍的双计数器解法，以及 dp[i] 表示以 i 结尾最长有效长度的动态规划解法，思路殊途同归。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条，下面每一帧都在套它。栈底永远是“当前这段的左边界”。
上排是输入串（固定不变），下面竖栈里存的是“下标”。栈底 -1 是哨兵，代表“有效段的左边界在 -1 之后”。
第 0 个是 ')'，弹完栈空了 → 它没人配，自己当“断点”，把下标 0 压进去做新的左边界。
第 1 个是 '('，还不知道谁来配它，先把下标 1 压栈占位。
第 2 个是 ')'，弹掉一个后栈顶是 0，说明从 1 到 2 这段是合法的，长度 2。当前最长 = 2。
第 3 个是 '('，还不知道谁来配它，先把下标 3 压栈占位。
第 4 个是 ')'，弹掉一个后栈顶是 0，说明从 1 到 4 这段是合法的，长度 4。当前最长 = 4。
第 5 个是 ')'，弹完栈空了 → 它没人配，自己当“断点”，把下标 5 压进去做新的左边界。
第 6 个是 '('，还不知道谁来配它，先把下标 6 压栈占位。
第 7 个是 ')'，弹掉一个后栈顶是 5，说明从 6 到 7 这段是合法的，长度 2。当前最长 = 4。
第 8 个是 '('，还不知道谁来配它，先把下标 8 压栈占位。
第 9 个是 '('，还不知道谁来配它，先把下标 9 压栈占位。
第 10 个是 ')'，弹掉一个后栈顶是 8，说明从 9 到 10 这段是合法的，长度 2。当前最长 = 4。
第 11 个是 ')'，弹掉一个后栈顶是 5，说明从 6 到 11 这段是合法的，长度 6。当前最长 = 6。
第 12 个是 '('，还不知道谁来配它，先把下标 12 压栈占位。
第 13 个是 ')'，弹掉一个后栈顶是 5，说明从 6 到 13 这段是合法的，长度 8。当前最长 = 8。
第 14 个是 '('，还不知道谁来配它，先把下标 14 压栈占位。
第 15 个是 '('，还不知道谁来配它，先把下标 15 压栈占位。
第 16 个是 ')'，弹掉一个后栈顶是 14，说明从 15 到 16 这段是合法的，长度 2。当前最长 = 8。
第 17 个是 '('，还不知道谁来配它，先把下标 17 压栈占位。
第 18 个是 ')'，弹掉一个后栈顶是 14，说明从 15 到 18 这段是合法的，长度 4。当前最长 = 8。
第 19 个是 ')'，弹掉一个后栈顶是 5，说明从 6 到 19 这段是合法的，长度 14。当前最长 = 14。
走完全串，过程中量到的最大长度就是答案：最长有效括号子串长度 = 14。
边界先想清。
两个高频追问。
参考代码
def longestValidParentheses(s: str) -> int: stack = [-1] # 先压左边界 best = 0 for i, c in enumerate(s): if c == "(": stack.append(i) # 压下标占位 else: stack.pop() if stack: best = max(best, i - stack[-1]) else: stack.append(i) # 新边界 return best复杂度
- 时间：O(n)，每个字符进出栈各一次
- 空间：O(n)，最坏全是左括号都压下标
易错点
面试追问把动画讲成自己的话
追问为什么栈里存下标而不是括号？
追问除了栈还有别的解法吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大矩形
LeetCode 85 · 困难 · 沿着 栈 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题