“最长有效括号”这道题，在力扣 Hot 100 题单里排在第 90 位，题号是 32。只要刷过动态规划或者栈相关题目的朋友，大概率都在这道题上卡过。它不像“判断括号是否有效”那么直白，难点两个字：最长。一旦要求的是“最长连续有效子串”，很多常规思路就全废了，因为你不仅要验证一段括号是否合法，还要在整串里找长度最大的那一段。
先说我能给出的最快结论：这道题最稳的做法是栈，空间 O(n)，面试时最好讲栈；动态规划适合理解“状态转移”的套路；双计数器正反扫描是空间 O(1) 的骚操作，笔试场景下非常加分。这篇我会把三种解法全部拆开，配合执行过程、易错点、排查思路，一次把这道题吃透。
1. 题目到底在问什么：先理解“连续有效子串”这个核心
1.1 题目信息速览
给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。
几个核心限制：
- 输入字符串长度最大为 3×10^4；
- 只包含左右括号两种字符；
- 要求的是子串，不是子序列；
- 子串必须连续，且括号匹配合法。
几个典型的输入输出：
| 输入 | 输出 | 解释 |
|---|---|---|
"(()" | 2 | 最长有效子串是"()"，长度 2 |
")()())" | 4 | 最长有效子串是"()()"，长度 4 |
"()(()" | 2 | 虽然开头是"()"，但后面的"(()"不完整，最长仍然只有 2 |
"" | 0 | 空串返回 0 |
看到"()(()"这个例子，很多人第一反应是“整串里左括号和右括号数量不都是 3 和 2 吗？那不是应该找最长的某一截？”这就是第一个坑：有效括号子串必须连续，不能跳过任何字符。
1.2 连续子串与子序列的本质区别
如果你做过“最长有效括号子序列”这类变体，你会知道子序列可以用计数器贪心解决，统计能匹配上的括号对就行，因为你可以跳过中间的坏括号。
但子串不行。子串意味着你要在原字符串里截取连续的一段，这一段中每个括号都得参与匹配。换句话说：
任何一个
)出现时，如果它前面没有足够多的未匹配(，它就会把整个区间“截断”。
我习惯把这种“截断”理解成断点。比如：
) ( ) ( ) )索引 0 的右括号直接断掉，左边界从索引 1 才开始；索引 5 的右括号再次断掉，因为它发现前面没有多余的左括号了。两次断点之间是()()，长度 4，这就是答案。
所以整个算法的本质就是：找到每个断点，统计相邻断点之间的最大长度。三种解法其实都在解决同一件事，只是用不同的数据结构记录断点位置。
1.3 为什么暴力法不可行
一个最朴素的暴力思路是：枚举所有子串的起点i和终点j，然后用一个计数器验证s[i..j]是否有效。
验证一段括号串是否有效很简单：从左往右扫，遇到(加一，遇到)减一，如果中途计数为负数则无效，最后计数必须为 0。
但枚举所有子串是 O(n^2)，每个子串再验证一遍 O(n)，整体 O(n^3)。在 n=3×10^4 的规模下，这个复杂度大约在 10^13 级别，哪怕每个操作只花 1 纳秒，也要好几个小时，显然是没法接受的。
暴力法唯一的价值，是帮我们确认了一个关键事实：有效的子串一定是一段连续的区间，而区间的左右边界由“不匹配”的括号决定。后面所有优化都是围绕怎么更快地找到这些边界展开的。
2. 解法一：栈——一个哨兵索引串起全部状态
2.1 核心思路：栈里存下标而不是括号本身
判断括号匹配最经典的方式就是栈：遇(入栈，遇)出栈。如果直接拿栈来求最长有效括号，很多人会这么做：遇到(入栈，遇到)弹出一个(，然后统计栈里还剩多少个括号。但这样做会掉进坑里，因为“匹配成功”和“匹配失败”的分界点并没有被精确记录。
正确的做法是：栈中保存字符下标，而不是字符本身。
我强烈建议你记住下面这句话：
栈底始终保存着“当前连续有效括号子串的前一个位置”的索引，也就是哨兵。
为什么需要这个哨兵？因为当我们遇到一个)时，如果能弹出一个(来和它匹配，说明从“上一个断点后面”到当前位置之间形成了一个新的有效区间。这个区间的长度就是当前下标 - 栈顶元素。栈顶元素正好是最近一个未匹配的字符位置，它标记了当前区间的左边界。
如果弹出后栈为空，说明当前这个)没有匹配的(，它自己就是一个新的断点。此时要把当前下标压入栈，作为新的哨兵。
2.2 完整实现与“弹出后栈空”的分支处理
直接上代码，我用 Java 写：
public int longestValidParentheses(String s) { Deque<Integer> stack = new ArrayDeque<>(); // 预置哨兵 -1，表示整个字符串起点之前的位置 stack.push(-1); int max = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { // 左括号入栈，等待匹配 stack.push(i); } else { // 右括号：先弹出栈顶元素 stack.pop(); if (stack.isEmpty()) { // 弹出后栈空，说明这个右括号没有匹配到左括号 // 它自己成为新的断点，压入作为新哨兵 stack.push(i); } else { // 栈不为空，说明匹配成功 // 当前有效子串长度为 i - 栈顶下标 max = Math.max(max, i - stack.peek()); } } } return max; }整个过程我拿")()())"手动走一遍：
| 当前下标 | 字符 | 操作 | 栈内容（自顶向下） | max 变化 |
|---|---|---|---|---|
| 初始化 | - | 预置哨兵 | [-1] | 0 |
| 0 | ) | 弹出 -1，栈空，压入 0 | [0] | 0 |
| 1 | ( | 压入 1 | [1, 0] | 0 |
| 2 | ) | 弹出 1，栈非空，栈顶为 0 | [0] | 2 |
| 3 | ( | 压入 3 | [3, 0] | 2 |
| 4 | ) | 弹出 3，栈非空，栈顶为 0 | [0] | 4 |
| 5 | ) | 弹出 0，栈空，压入 5 | [5] | 4 |
最终答案是 4，正确。
这里最关键的分支就是“弹出后栈空”这一步。有些初学者会漏掉，导致遇到没有匹配的右括号时，下一次计算长度以它为基准，结果算出一个错误的超大长度。
2.3 为什么栈底要预置 -1
很多人第一次看到stack.push(-1)都会疑惑，字符串里又没有下标 -1，放进去干嘛？
其实 -1 就是一个虚拟哨兵，它代表“整个字符串起点之前的位置”。这样做的好处是，当有效子串从字符串开头就成立时，比如"()"，扫描到下标 1 时弹出下标 0，栈顶剩下 -1，于是长度等于1 - (-1) = 2。
如果没有这个 -1，遇到"()"这种用例，弹出后栈直接为空，代码就进入了“压入当前下标”分支，答案变成 0，直接错了。
所以记住：预置 -1 是为了处理从开头就匹配的边界情况。这算是栈解法里一个不算难、但特别容易忽略的细节。
还有一个细节：用 Deque 而不是 Stack。Java 的 Stack 是继承自 Vector 的同步类，有同步开销，实际刷题中用 ArrayDeque 实现栈更轻量。不过面试时如果你直接写
Stack<Integer> stack = new Stack<>()，面试官一般也不会深究，能跑就行。
3. 解法二：动态规划——以每个位置结尾的局部最优解
3.1 状态定义：dp[i] 表示以 s[i] 结尾的最长有效子串长度
动态规划的核心是先定义状态。对于连续子串类问题，我总结出一个通用套路：
如果题目要求“以某个位置结尾的某种状态”，状态定义里通常要带“以 i 结尾”这个限定。
所以这里定义：
dp[i]表示以s[i]结尾的最长有效括号子串的长度。
为什么必须以 s[i] 结尾？因为只有保证“结尾位置已知”，才能把新字符接续到前面已有的结果上，形成递推。
如果s[i]是'('，那么以它结尾的子串不可能有效，直接dp[i] = 0。
如果s[i]是')'，情况就要分两类讨论。
3.2 递推公式的两种匹配场景
场景一：s[i-1]是'('
这种情况最简单，形如" ... ()"。那么s[i-1]和s[i]直接配对，前面的部分就是s[0..i-2]，所以：
dp[i] = dp[i-2] + 2注意：如果i < 2，dp[i-2]不存在，等价于 0。
举例："()"，i=1 时，dp[1] = dp[-1] + 2 = 2。
场景二：s[i-1]是')'
这种情况形如" ... ))"。当前字符想要和更前面的某个'('配对，那这个'('必须先跳过s[i-1]这一整段有效区间。
假设以s[i-1]结尾的有效区间长度为dp[i-1]，那么这个有效区间的起点是i - dp[i-1]。当前)想配对，就得看i - dp[i-1] - 1这个位置是不是'('。
如果这个位置确实是'('，那么：
dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]这里最后加上的dp[i - dp[i-1] - 2]，是把'('前面那段连续有效区间也拼接进来。
我拿"()(())"举例子：
| 索引 | 字符 | dp[i] 计算过程 |
|---|---|---|
| 0 | ( | dp[0] = 0 |
| 1 | ) | s[0] 是(，dp[1] = dp[-1]+2 = 2 |
| 2 | ( | dp[2] = 0 |
| 3 | ( | dp[3] = 0 |
| 4 | ) | s[3] 是(，dp[4] = dp[2]+2 = 2 |
| 5 | ) | s[4] 是)，left = 5 - dp[4] - 1 = 2，s[2] 是(，dp[5] = dp[4] + 2 + dp[1] = 2+2+2 = 6 |
最终dp[5] = 6，整串长度为 6，完全正确。
场景二特别容易漏掉最后那段dp[i - dp[i-1] - 2]，也就是'('之前如果还连着一段有效括号区间，必须拼接上。
3.3 代码实现与越界保护
public int longestValidParentheses(String s) { int n = s.length(); int[] dp = new int[n]; int max = 0; for (int i = 1; i < n; i++) { // 只有右括号可能出现有效结尾 if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { // 场景一：直接与前面组成 () dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else { // 场景二：找到可能配对的位置 int left = i - dp[i - 1] - 1; if (left >= 0 && s.charAt(left) == '(') { dp[i] = dp[i - 1] + 2 + (left - 1 >= 0 ? dp[left - 1] : 0); } } max = Math.max(max, dp[i]); } // s.charAt(i) == '(' 时 dp[i] 保持 0，无需处理 } return max; }动态规划的易错点非常集中：
dp[i-2]在i < 2时会越界，需要先判断；left-1在left == 0时会越界，也需要判断；left位置必须是'('才算匹配成功，不能想当然直接计算；- 只有当
s[i]是')'时才可能更新答案。
这个解法理解起来比栈稍难，但它在 LeetCode 讨论区里的出镜率很高，因为动态规划是面试官最爱追问的思路之一。如果你能现场把状态定义和两种场景讲清楚，会是一个明显的加分项。
4. 解法三：双计数器正反扫描——空间复杂度压到 O(1)
4.1 从左到右：right 大于 left 时重置
前面两种解法都用到了额外空间。这道题还有一个非常巧妙的 O(1) 空间解法，思路也简单：用两个计数器 left 和 right，分别记录当前遇到的'('和')'数量。
从左往右遍历时：
- 遇到
'('，left++； - 遇到
')'，right++； - 如果 left == right，说明当前扫描的这段子串是有可能有效的（括号数量匹配），更新
max = max(left * 2, max)； - 如果 right > left，说明右括号已经多于左括号，本段不可能继续匹配，直接全部清零，从下一个位置重新开始。
这个方法的核心逻辑是：从左往右扫描时，只要右括号数量超过左括号，这段就一定不可能是有效子串了，直接切断。它本质上也是在找“断点”，只是用计数而不是栈来记录。
4.2 从右到左：补上奇数左括号场景
如果只从左往右扫一遍，会漏掉一类情况：左括号一直多于右括号的字符串，比如"(()"。
从左往右扫：
- 左括号、左括号、右括号，整个过程 right 永远没有超过 left，计数器永远不会清零；
- 当 left==right 时，left=2, right=1，不相等，也更新不了正确长度；
- 最终 max 还是 0，但正确答案是 2。
这个问题的根源在于：从左往右扫描天然无法处理“左括号过多”这种不对称情况。解决办法就是把字符串反向再扫一遍，从右往左遍历时对称处理：
- 遇到
')'时 right++； - 遇到
'('时 left++； - 如果 left == right，更新 max；
- 如果 left > right，说明左括号过多，直接清零。
这样“左括号过多”的段在反向扫描中就能被正确识别和切断。
4.3 代码实现与“为什么要扫两遍”的证明思路
public int longestValidParentheses(String s) { int left = 0, right = 0; int max = 0; // 从左到右扫描，处理右括号过多的情况 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, left * 2); } else if (right > left) { left = 0; right = 0; } } // 从右到左扫描，处理左括号过多的情况 left = 0; right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, left * 2); } else if (left > right) { left = 0; right = 0; } } return max; }拿"(()"验证一下：反向扫描时，从右往左：)right=1，(left=1，left==right，更新 max=2；再往左一个(，left=2，right=1，此时 left > right，清零。最终 max=2，正确。
证明为什么需要两遍的简洁说法：
- 从左往右扫描，能准确切断“右括号过多”的无效段；
- 从右往左扫描，能准确切断“左括号过多”的无效段；
- 一个无效段总有一侧会表现为“某种括号过多”，所以两遍扫描覆盖了所有断点。
这个解法最妙的地方是空间复杂度真正做到了 O(1)。在 LeetCode 上，这种解法对付 3×10^4 的数据规模完全够用，而且代码量也很短。
5. 三种解法对比与实战选择
5.1 复杂度与代码量对照表
| 解法 | 时间复杂度 | 空间复杂度 | 代码量 | 易错点 |
|---|---|---|---|---|
| 栈 | O(n) | O(n) | 短 | 忘记预置 -1，弹出后栈空忘记压入当前下标 |
| 动态规划 | O(n) | O(n) | 中 | 越界防护多，场景二容易漏加拼接段 |
| 双计数器 | O(n) | O(1) | 短 | 只扫一遍会漏掉“左括号过多”的情况 |
时间上三者都是 O(n)，因为每个字符最多被访问常数次。空间上双计数器完胜。但面试时我并不建议一上来就写双计数器，因为它有点“奇技淫巧”的味道，不如栈和 DP 容易展示你的逻辑推导能力。
5.2 面试时怎么讲才能拿高分
以我个人的经验，这道题在面试中的标准答题流程是：
- 先描述暴力解法：枚举所有子串，验证是否有效，复杂度 O(n^3)，作为 baseline；
- 引入栈解法：把每一个未匹配的右括号视作断点，栈底预置 -1 处理边界，讲清楚为什么栈里存下标；
- 主动补充动态规划解法：展示你掌握了另一种思路，重点讲状态定义和两个转移场景；
- 最后提一句双计数器：如果想优化空间，可以从左往右和从右往左各扫一遍。
这套流程从暴力到优化层层递进，面试官能清楚看到你的思考过程。很多人喜欢直接甩最优解，反而会被问住。先讲最笨但正确的思路，再逐步优化，是最安全的面试策略。
5.3 本题的进阶变体与扩展阅读
LeetCode 上括号相关的经典题目不少，我建议把这题和下面几道一起刷，效果更好：
- 20. 有效的括号：练习栈的基本用法，是本题的前置题；
- 22. 括号生成：回溯算法，理解合法括号序列的构造规则；
- 301. 删除无效的括号：BFS 或 DFS 的应用，困难题进阶；
- 32. 最长有效括号：也就是本题，栈、DP、双指针三种解法横向比较。
这几道题串起来刷完，你会对“括号匹配”这个家族题有整体认识，比单纯背代码有效得多。
6. 常见问题与调试实录
6.1 栈解法教科书式易错点
我先说一个我自己第一次刷这题时踩过的坑："()()"这个用例，用栈解法走一遍，答案应该是 4。但如果省略了预置 -1，第一次弹出后栈空，你直接压入当前右括号的下标，最后答案就变成 0。
还有一种错误写法是：弹出后不管栈空不空，都用i - stack.peek()计算长度。遇到没有匹配的右括号时，stack.peek()是它自己，算出来的长度是 0，看起来结果不会错，但下一次计算时断点位置就乱了，比如"())()"这类用例会算错。
调试栈解法时，我的建议是把每一轮操作后的栈打印出来，重点看：
- 每次遇到
)后，栈是否为空； - 栈空时是否压入了当前下标；
- 非空时是否用
peek()而不是pop()计算长度。
6.2 DP 状态迁移越界的三种排查
DP 解法出错，绝大多数情况都出在数组越界上。最常见的三个位置：
dp[i - 2]：当 i 等于 1 时越界，需要i >= 2判断；s.charAt(left)：left 可能等于 -1，需要left >= 0判断；dp[left - 1]：left 等于 0 时越界，需要left - 1 >= 0判断。
这三个点如果写错，不是数组越界异常就是答案偏小。我的调试技巧是准备几个字符串用例逐一验证：
"()" -> 2 ")()())" -> 4 "()(()" -> 2 ")(()())(" -> 6如果手推结果和代码输出不一致，再用打印 dp 数组的方式定位到具体是哪个场景算错了。
6.3 双计数器漏掉“(()”这类用例的原因排查
双计数器解法最常见的错误是只写从左到右的那一遍。这个时候"(()"的输出是 0，而正确结果是 2。
排查方法很简单：拿"(()"手推一遍，你会发现 left 一直大于 right，计数器永远不会被清零，也永远不满足 left == right，最后 max 停留在 0。
反向扫描正好解决这个问题。我还见过有人把反向扫描的判断条件写错，写成if (right > left)清零，结果依然错。反向时对称条件应该是left > right时清零，因为反向扫描时左括号过多才是无效信号。
调试这个解法时，我建议准备一组“左括号偏多”和“右括号偏多”的用例各一个，分别验证两个方向是否正确：
- 左括号偏多：
"(()"、"((())"； - 右括号偏多：
"())"、")()())"。
7. 从这题扩散开来：一类“最长连续有效子串”问题的方法论
7.1 连续子串问题的通用思考框架
刷多了你会发现，这道题背后其实藏着一类问题：求满足某种条件的最长连续子串。这类问题有一个通用框架：
- 先想“以 i 结尾”的状态怎么定义；
- 再想新字符如何根据前面的状态转移；
- 最后看能不能用双指针或计数器压缩空间。
栈解法的本质是“维护最近的未匹配位置”，DP 解法的本质是“记录以每个位置结尾的最长有效长度”，双计数器解法的本质是“在数量失衡处切断”。
把这三种思考方式记住，遇到其他连续子串问题，比如“和为 K 的子数组”“最长连续递增序列”“最长无重复字符子串”，你都至少能想出两种解法。
7.2 与括号家族其他题目的横向对比
| 题目 | 核心考点 | 与本题的关系 |
|---|---|---|
| 有效的括号 | 栈的基础使用 | 本题的前置基础 |
| 最长有效括号 | 栈 / DP / 双指针 | 本题 |
| 括号生成 | 回溯 / 递归 | 帮助理解合法括号序列结构 |
| 删除无效的括号 | BFS / DFS | 在本题基础上加了删除操作 |
我个人刷题的一个习惯是：遇到“判断类”题目，就先问自己有没有对应的“最长”版本；遇到“构造类”题目，就问自己有没有“判断”和“最长”版本。比如知道了怎么判断括号有效，就应该主动去找最长有效括号，这样知识才是成网的，而不是一题一题孤零零地记。
这道题后续还可以扩展的方向是：如果字符串不是从下标 0 开始，而是环形怎么办？如果括号种类从一种增加到三种怎么办？这些变体在面试中出现频率不高，但一旦出现，前面三种思路的基本功就会直接决定你能不能做出来。栈、DP、双指针三种解法都掌握之后，再遇到这些变体，你至少不会毫无头绪。
