“最长有效括号”这道题在力扣 Hot 100 题单里排在第 90 位题号是 32。只要刷过动态规划或者栈相关题目的朋友大概率都在这道题上卡过。它不像“判断括号是否有效”那么直白难点两个字最长。一旦要求的是“最长连续有效子串”很多常规思路就全废了因为你不仅要验证一段括号是否合法还要在整串里找长度最大的那一段。先说我能给出的最快结论这道题最稳的做法是栈空间 O(n)面试时最好讲栈动态规划适合理解“状态转移”的套路双计数器正反扫描是空间 O(1) 的骚操作笔试场景下非常加分。这篇我会把三种解法全部拆开配合执行过程、易错点、排查思路一次把这道题吃透。1. 题目到底在问什么先理解“连续有效子串”这个核心1.1 题目信息速览给你一个只包含(和)的字符串找出最长有效格式正确且连续括号子串的长度。几个核心限制输入字符串长度最大为 3×10^4只包含左右括号两种字符要求的是子串不是子序列子串必须连续且括号匹配合法。几个典型的输入输出输入输出解释(()2最长有效子串是()长度 2)()())4最长有效子串是()()长度 4()(()2虽然开头是()但后面的(()不完整最长仍然只有 20空串返回 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)。在 n3×10^4 的规模下这个复杂度大约在 10^13 级别哪怕每个操作只花 1 纳秒也要好几个小时显然是没法接受的。暴力法唯一的价值是帮我们确认了一个关键事实有效的子串一定是一段连续的区间而区间的左右边界由“不匹配”的括号决定。后面所有优化都是围绕怎么更快地找到这些边界展开的。2. 解法一栈——一个哨兵索引串起全部状态2.1 核心思路栈里存下标而不是括号本身判断括号匹配最经典的方式就是栈遇(入栈遇)出栈。如果直接拿栈来求最长有效括号很多人会这么做遇到(入栈遇到)弹出一个(然后统计栈里还剩多少个括号。但这样做会掉进坑里因为“匹配成功”和“匹配失败”的分界点并没有被精确记录。正确的做法是栈中保存字符下标而不是字符本身。我强烈建议你记住下面这句话栈底始终保存着“当前连续有效括号子串的前一个位置”的索引也就是哨兵。为什么需要这个哨兵因为当我们遇到一个)时如果能弹出一个(来和它匹配说明从“上一个断点后面”到当前位置之间形成了一个新的有效区间。这个区间的长度就是当前下标 - 栈顶元素。栈顶元素正好是最近一个未匹配的字符位置它标记了当前区间的左边界。如果弹出后栈为空说明当前这个)没有匹配的(它自己就是一个新的断点。此时要把当前下标压入栈作为新的哨兵。2.2 完整实现与“弹出后栈空”的分支处理直接上代码我用 Java 写public int longestValidParentheses(String s) { DequeInteger 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]00)弹出 -1栈空压入 0[0]01(压入 1[1, 0]02)弹出 1栈非空栈顶为 0[0]23(压入 3[3, 0]24)弹出 3栈非空栈顶为 0[0]45)弹出 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 实现栈更轻量。不过面试时如果你直接写StackInteger 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 2dp[i-2]不存在等价于 0。举例()i1 时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] 01)s[0] 是(dp[1] dp[-1]2 22(dp[2] 03(dp[3] 04)s[3] 是(dp[4] dp[2]2 25)s[4] 是)left 5 - dp[4] - 1 2s[2] 是(dp[5] dp[4] 2 dp[1] 222 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计数器永远不会清零当 leftright 时left2, right1不相等也更新不了正确长度最终 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; }拿(()验证一下反向扫描时从右往左)right1(left1leftright更新 max2再往左一个(left2right1此时 left right清零。最终 max2正确。证明为什么需要两遍的简洁说法从左往右扫描能准确切断“右括号过多”的无效段从右往左扫描能准确切断“左括号过多”的无效段一个无效段总有一侧会表现为“某种括号过多”所以两遍扫描覆盖了所有断点。这个解法最妙的地方是空间复杂度真正做到了 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、双指针三种解法都掌握之后再遇到这些变体你至少不会毫无头绪。
最长有效括号全解：栈、动态规划与双计数器实现
“最长有效括号”这道题在力扣 Hot 100 题单里排在第 90 位题号是 32。只要刷过动态规划或者栈相关题目的朋友大概率都在这道题上卡过。它不像“判断括号是否有效”那么直白难点两个字最长。一旦要求的是“最长连续有效子串”很多常规思路就全废了因为你不仅要验证一段括号是否合法还要在整串里找长度最大的那一段。先说我能给出的最快结论这道题最稳的做法是栈空间 O(n)面试时最好讲栈动态规划适合理解“状态转移”的套路双计数器正反扫描是空间 O(1) 的骚操作笔试场景下非常加分。这篇我会把三种解法全部拆开配合执行过程、易错点、排查思路一次把这道题吃透。1. 题目到底在问什么先理解“连续有效子串”这个核心1.1 题目信息速览给你一个只包含(和)的字符串找出最长有效格式正确且连续括号子串的长度。几个核心限制输入字符串长度最大为 3×10^4只包含左右括号两种字符要求的是子串不是子序列子串必须连续且括号匹配合法。几个典型的输入输出输入输出解释(()2最长有效子串是()长度 2)()())4最长有效子串是()()长度 4()(()2虽然开头是()但后面的(()不完整最长仍然只有 20空串返回 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)。在 n3×10^4 的规模下这个复杂度大约在 10^13 级别哪怕每个操作只花 1 纳秒也要好几个小时显然是没法接受的。暴力法唯一的价值是帮我们确认了一个关键事实有效的子串一定是一段连续的区间而区间的左右边界由“不匹配”的括号决定。后面所有优化都是围绕怎么更快地找到这些边界展开的。2. 解法一栈——一个哨兵索引串起全部状态2.1 核心思路栈里存下标而不是括号本身判断括号匹配最经典的方式就是栈遇(入栈遇)出栈。如果直接拿栈来求最长有效括号很多人会这么做遇到(入栈遇到)弹出一个(然后统计栈里还剩多少个括号。但这样做会掉进坑里因为“匹配成功”和“匹配失败”的分界点并没有被精确记录。正确的做法是栈中保存字符下标而不是字符本身。我强烈建议你记住下面这句话栈底始终保存着“当前连续有效括号子串的前一个位置”的索引也就是哨兵。为什么需要这个哨兵因为当我们遇到一个)时如果能弹出一个(来和它匹配说明从“上一个断点后面”到当前位置之间形成了一个新的有效区间。这个区间的长度就是当前下标 - 栈顶元素。栈顶元素正好是最近一个未匹配的字符位置它标记了当前区间的左边界。如果弹出后栈为空说明当前这个)没有匹配的(它自己就是一个新的断点。此时要把当前下标压入栈作为新的哨兵。2.2 完整实现与“弹出后栈空”的分支处理直接上代码我用 Java 写public int longestValidParentheses(String s) { DequeInteger 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]00)弹出 -1栈空压入 0[0]01(压入 1[1, 0]02)弹出 1栈非空栈顶为 0[0]23(压入 3[3, 0]24)弹出 3栈非空栈顶为 0[0]45)弹出 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 实现栈更轻量。不过面试时如果你直接写StackInteger 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 2dp[i-2]不存在等价于 0。举例()i1 时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] 01)s[0] 是(dp[1] dp[-1]2 22(dp[2] 03(dp[3] 04)s[3] 是(dp[4] dp[2]2 25)s[4] 是)left 5 - dp[4] - 1 2s[2] 是(dp[5] dp[4] 2 dp[1] 222 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计数器永远不会清零当 leftright 时left2, right1不相等也更新不了正确长度最终 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; }拿(()验证一下反向扫描时从右往左)right1(left1leftright更新 max2再往左一个(left2right1此时 left right清零。最终 max2正确。证明为什么需要两遍的简洁说法从左往右扫描能准确切断“右括号过多”的无效段从右往左扫描能准确切断“左括号过多”的无效段一个无效段总有一侧会表现为“某种括号过多”所以两遍扫描覆盖了所有断点。这个解法最妙的地方是空间复杂度真正做到了 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、双指针三种解法都掌握之后再遇到这些变体你至少不会毫无头绪。