企业官网建设流程全解析

最长有效括号，力扣第32题，在热题100里属于那种一眼看上去很基础、上手一写就翻车的题目。题目描述只有一句话：给定一个只包含(和)的字符串，返回最长有效括号子串的长度。所谓的"有效括号子串"，要求格式正确且连续，比如(()里最长的是()，答案是2；)()())里最长的是()()，答案是4。这道题真正难的地方在于，它不是在数括号数量够不够，而是要在一段连续子串上做严格匹配，而且经典的解法能一路从暴力、栈、动态规划写到 O(1) 空间的双向计数，几乎把算法面试里最常见的几类思维模式全串起来了。

这篇文章我会用 Java 把三种主流解法完整走一遍：栈解法、动态规划解法、双向计数解法。每种解法都会说清楚为什么这么设计、代码每一行为什么要这样写、复杂度怎么算，以及我在实际刷题和面试复盘里踩过的坑。不管你是刚开始刷力扣热题100的新手，还是准备 Java 后端面试、想把手上的题解体系化整理的老手，这篇都能给你一份可以直接复用的思路框架。

1. 问题本质与暴力思路拆解（为什么不能直接数括号数量）

1.1 先吃透"有效括号子串"这个定义

很多初学者拿到这道题，第一反应是数左右括号的个数，觉得只要左括号等于右括号就是有效。这个直觉在判断"整个字符串是否是合法括号序列"时是成立的，但放在"最长有效子串"这道题里就完全不够了，因为题目里有两个限定词：有效和连续。

先看"有效"。一个括号子串有效，意味着任意前缀中右括号的数量不能超过左括号，并且最终左右数量相等。换句话说，这是一对对括号的正确嵌套，像()(())、(()())、((()))都是有效串，而())(()、(()))(都不是。这个"任意前缀右括号不超左括号"的条件，是后面所有解法里判断是否该重置的根因。

再看"连续"。子串要求索引连续，位置必须挨着，不能跳过中间的非法字符。这一点让题目从"计数"变成了"在连续区间里找合法片段"。比如)()())这个字符串，整体不是一个有效括号串，但它包含连续的有效片段()()，长度是4。我们要找的就是这种夹在无效字符之间的合法片段，而不是把字符串里散落的括号凑起来。有些变体题会问"最长有效括号子序列"，那个允许跳着选，答案直接用双计数器就能算出来；但热题100这道题明确是子串，必须连续，难度一下子就上来了。

还有一个常见的理解偏差：())里最长有效子串是()，长度为2，不是把())当成一个整体去看。也就是说我们要在所有可能的连续子串里，挑出长度最大的那一个合法片段。这个"片段"概念贯穿始终，栈解法里的栈底元素、动态规划里的dp[i]、双向计数里的计数器重置，本质上都是在追踪"当前合法片段的边界在哪里"。

1.2 暴力解法与 O(n²) 的改良写法

暴力思路是最直观的：枚举所有起点和终点，切出所有子串，逐个检查是否是有效括号串，取最大长度。枚举子串本身是 O(n²)，每次检查又要从头扫一遍做括号匹配判断，整体就是 O(n³)。n 小时无所谓，但力扣上这道题的数据范围是字符串长度最大 3×10⁴，O(n³) 直接超时，没有任何优化余地。

暴力也能改得聪明一点，降成 O(n²)：固定起点，不断向右扩展终点，同时维护left和right两个计数器。遇到(就 left++，遇到)就 right++。如果某个时刻 right 大于 left，说明以当前起点到这里的这段子串已经不可能再成为有效括号串了，因为右括号多了，直接 break 掉换下一个起点。如果 left 等于 right，说明当前这段是有效的，记录长度。这样每个起点最多扫一遍，总体是 O(n²)。

for (int i = 0; i < n; i++) { int left = 0, right = 0; for (int j = i; j < n; j++) { if (s.charAt(j) == '(') left++; else right++; if (right > left) break; if (left == right) max = Math.max(max, left + right); } }

这个 O(n²) 版本虽然是过渡方案，但它在思维上非常重要：它揭示了"合法片段中断的唯一原因是右括号数量超过了左括号"这一规律。后面三种优化解法，本质上都是在用不同的数据结构或策略，去高效处理这个"超越即失效"的边界。我建议你写代码前先在纸上跑一遍这个暴力版本，把(()和)()())两个例子都走一遍，你就知道答案的 2 和 4 到底是从哪里冒出来的了。

2. 栈解法：用下标而不是括号本身求最长有效括号

2.1 为什么栈里要存索引而不是括号字符

栈是处理括号匹配问题的天然工具，因为括号的最近匹配特性和栈的 LIFO 特性完全一致：遇到左括号压栈，遇到右括号弹栈，弹出去的左括号就是"最近一个还没匹配的左括号"。但在这道题里，栈里存的不是字符，而是括号在字符串中的索引下标。

原因很简单：题目要的是长度，而长度必须通过下标相减得到。如果栈里只存括号字符(，那么弹栈之后我们根本不知道这个左括号在字符串的哪个位置，也就没法计算子串长度。存下标之后，当右括号弹掉一个左括号下标j时，以这个右括号结尾的有效子串长度可以直接用i - j + 1表示吗？其实不行，因为弹出之后栈里还有更早的左括号或者边界标记，真正的答案是i - stack.peek()。

这就引出了栈解法最精髓的一步：初始化时先压入一个 -1。这个 -1 是一个哨兵，代表"当前合法片段的起点前一个位置"。当遇到右括号并且弹出的是哨兵时，栈空了，说明这个右括号没有匹配对象，它是一个"断裂点"，我们需要把当前下标 i 压入栈，作为新的哨兵，也就是新的合法片段起点前一位。

举个具体例子，字符串()：索引0是左括号，压栈，栈变成[-1, 0]；索引1是右括号，弹栈，弹出0，此时栈顶是哨兵 -1，长度就是1 - (-1) = 2，刚好是整个子串的长度。如果没有哨兵 -1，这个长度就算不出来，因为栈只有一个元素被弹掉了，栈空之后没有参照位置。这就是哨兵的意义：它始终指向当前扫描到的合法片段的最左边界。

2.2 栈解法 Java 代码与手工推演

下面是完整的 Java 实现，我用的是ArrayDeque作为栈，注意它不是线程安全的，但单线程刷题完全够用，而且性能比Stack类更好，Stack本身继承自Vector，有同步开销，力扣上用ArrayDeque是主流选择。

class Solution { public int longestValidParentheses(String s) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(-1); int max = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) { stack.push(i); } else { max = Math.max(max, i - stack.peek()); } } } return max; } }

这个解法的时间复杂度是 O(n)，每个字符最多入栈出栈一次；空间复杂度是 O(n)，栈最多压入 n 个下标。逻辑上只有四个分支，非常简洁，但越是简洁的代码越容易在细节上出错。我们用手工推演跑一遍)()())，看看长度4是怎么得出来的：

• i=0，字符)，弹出栈顶的 -1，栈空，把0压入栈。栈：[0]。此时0作为新的断裂点。
• i=1，字符(，压栈。栈：[0, 1]。
• i=2，字符)，弹出1，栈顶是0，长度2-0=2，max 更新为2。栈：[0]。
• i=3，字符(，压栈。栈：[0, 3]。
• i=4，字符)，弹出3，栈顶是0，长度4-0=4，max 更新为4。栈：[0]。
• i=5，字符)，弹出0，栈空，把5压入栈。max 仍是4。

最终答案4，完美对应子串()()的长度。注意这里最关键的一点：i=2 的时候，我们并没有从0这个断裂点重新开始计数，而是通过i - stack.peek()直接跨过断裂点之前的所有内容。因为断裂点0本身是无效字符，它不参与任何合法片段，所以它只作为边界参照存在。这种"用栈底元素记录边界"的思路，正是这道题和普通括号匹配题最大的区别。

2.3 栈解法最容易写错的三个点

第一，忘记初始化 -1。如果你上来就stack.push(0)并且循环从1开始，边界处理会变得非常别扭，一旦遇到首字符是右括号的情况，栈就会出问题。统一在循环前压入 -1，让它作为虚拟边界，代码会干净得多，所有情况都能统一处理。

第二，用Stack<Character>存字符而不是存下标。这是新手最容易犯的错误，存字符的话等到要计算长度时才发现根本没有位置信息，只能临时改代码。宁可先想清楚再动手，刷题时把"长度由下标差决定"这个意识刻在脑子里。

第三，右括号弹出后栈空的情况处理。很多人会把if (stack.isEmpty()) { stack.push(i); }这一步漏掉，觉得栈空了就让 max 保持原样就好。但如果不把当前右括号下标压栈作为新的断裂点，后面合法的()子串就无法正确定位起点。比如)()()这个例子，如果漏掉这一步，后面的长度计算基准会乱掉，答案会偏大或偏小。这一步绝不是可选的，它是栈解法保持正确性的关键。

3. 动态规划解法：以 dp[i] 为结尾的状态推导细节

3.1 dp 数组的状态定义与两类转移方程

动态规划解法在很多题解里被列为基础解法，但实际面试中能把转移方程讲明白的人不多。我们先定义状态：dp[i]表示以索引 i 结尾的最长有效括号子串的长度。注意这个"以 i 结尾"是苛刻的，它要求这个子串的最后一个字符就是s.charAt(i)，所以如果s[i]是(，那么dp[i]直接就是0，因为任何有效括号串都不可能以左括号结尾。

状态定义清楚了，转移就只剩两种情况，而且都要求s[i]是)。

第一种情况：s[i]是)，且s[i-1]是(。这种情况最简单，i-1和i直接凑成了一对括号，那么以 i 结尾的最长有效串至少是2，如果i-2位置之前还有有效串，可以接上，所以转移方程是dp[i] = dp[i-2] + 2，当然要保证i-2不越界。

第二种情况：s[i]是)，且s[i-1]也是)。这说明当前这个右括号要匹配的，是它左边一段有效串之前的那个左括号。具体来说，先看dp[i-1]，它表示以i-1结尾的有效串长度，假设为 len，那么这段有效串覆盖的区间是[i-len, i-1]。在这段区间之前，即下标i-len-1的位置，如果是一个左括号，那么它就能和当前的s[i]配对，配对之后长度至少是dp[i-1] + 2，如果这个左括号前面还有有效串，也要接上，即再加上dp[i-len-2]。所以转移方程是：

dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]（需保证i-dp[i-1]-1 >= 0且该位置是左括号）

这个方程初看很绕，但拆开看非常清晰：dp[i-1]是内部那段已经配好的有效串，2 是外层新配的一对括号，dp[i-dp[i-1]-2]是外层括号拼接位置之前的有效串。整个式子就像一个三明治：前面已有的 + 新包的一层 + 中间已有的。

3.2 动态规划 Java 代码与完整推导

class Solution { 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 if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0); } max = Math.max(max, dp[i]); } } return max; } }

用(()())完整推一遍，长度6，帮助理解：

• i=1，s[1] 是)，s[0] 是(，第一种情况，dp[1] = dp[-1] + 2 = 2。表示()。
• i=2，s[2] 是(，跳过，dp[2] = 0。
• i=3，s[3] 是(，跳过，dp[3] = 0。
• i=4，s[4] 是)，s[3] 是(，第一种情况，dp[4] = dp[2] + 2 = 0 + 2 = 2。这里注意，dp[2]=0是因为索引2是孤立的左括号，所以以4结尾的有效串是子串()，从索引3到4。
• i=5，s[5] 是)，s[4] 是)，第二种情况。dp[4] = 2，检查i - dp[i-1] - 1 = 5 - 2 - 1 = 2，s[2] 是(，成立。于是dp[5] = dp[4] + 2 + dp[5 - dp[4] - 2] = 2 + 2 + dp[1] = 2 + 2 + 2 = 6。

到 i=5 时，整个(()())被完整匹配，答案6。仔细体会最后一步：内部有效串是索引3-4的()（长度2），索引2的左括号和索引5的右括号配成外层一对，索引0-1的()（长度2）作为前缀接上，三个部分加起来就是6。

边界条件上要特别小心：i - dp[i-1] - 1可能等于 -1，说明左边没有字符了，这时不能访问数组；i - dp[i-1] - 2同理。我用三目运算符做了保护，这是写这类题目最常踩的坑，稍微不留神就 ArrayIndexOutOfBoundsException。另一个细节是 dp 数组默认是0，所以左括号位置的 dp 值天然是0，不需要显式赋值。

3.3 面试里讲 DP 思路的推荐顺序

动态规划是面试官最喜欢的追问方向，因为它能考察候选人有没有真正理解状态设计。我的建议是讲的时候按这个顺序来：先说状态定义——"dp[i] 表示以 i 结尾的最长有效括号子串长度"；然后说为什么左括号位置 dp 为0；接着分两类讨论右括号的情况，画一个字符串的括号配对图，指着图说明第一类是最简单的相邻配对，第二类是嵌套匹配需要借助 dp[i-1] 跳过内部区间；最后强调边界保护和复杂度 O(n)。

有一个常见的讲解误区是把第二种情况讲成"看 s[i-1] 是不是左括号"，完全不对。s[i-1]是右括号时，也可能匹配成功，比如(())这种嵌套结构，最后一个右括号匹配的是整个内部有效串之前的左括号。所以第二类才是这道题的精髓，也是 DP 解法区别于其它解法的关键，你能不能把这一条讲清楚，面试官立刻就能判断出你是背的答案还是真懂。

4. 双向计数法：空间复杂度 O(1) 的最长括号解法

4.1 单向计数为什么算不满答案

如果能想到栈和 DP，其实这道题已经能过了。但热题100里的好题通常会有追问：能不能把空间复杂度降到 O(1)？双向计数就是为这个问题准备的。

思路是用两个计数器 left 和 right 扫描字符串。遇到(就 left++，遇到)就 right++。当 left 等于 right 时，说明当前这一段左右抵消，是一个有效括号串，长度就是2 * right，更新最大值。当 right 大于 left 时，说明从某个起点开始，右括号已经超过了左括号，这一段从该起点开始"彻底没救了"，直接把 left 和 right 清零，从下一个位置重新开始计数。

这个单向扫描的思路很自然，但它有一个致命缺陷：它只能处理"右括号太多"导致的片段断裂，处理不了"左括号一直太多"的情况。最典型的例子是(()：从左往右扫，i=0 left=1，i=1 left=2，i=2 right=1，全程 left 始终大于 right，永远不会触发重置，也永远不会 left 等于 right，所以答案一直是0。但实际上这个字符串里的()长度是2，被漏掉了。

问题出在哪？因为(()里多了一个左括号，而这个左括号在正向扫描中会被一直"背"在身上，导致左右永远无法相等。要想解决它，就得让"多出来"的左括号从另一个方向被消耗掉——这就有了反向扫描。

4.2 双向计数 Java 代码与原理说明

class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, max = 0; int n = s.length(); for (int i = 0; i < n; i++) { if (s.charAt(i) == '(') left++; else right++; if (left == right) { max = Math.max(max, 2 * right); } else if (right > left) { left = 0; right = 0; } } left = 0; right = 0; for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == '(') left++; else right++; if (left == right) { max = Math.max(max, 2 * left); } else if (left > right) { left = 0; right = 0; } } return max; } }

反向扫描和正向扫描完全对称：从右往左走，遇到(让 left++，遇到)让 right++，当 left 等于 right 时更新2 * left。触发重置的条件变成left > right，因为从右往左看，如果左括号数量超过了右括号，说明这一段从右边起头"没救了"，同样清零重新计。

用(()再验证一次反向扫描：从右往左，i=2 是)，right=1；i=1 是(，left=1，left 等于 right，max = 2；i=0 是(，left=2，此时 left 大于 right，触发重置。最终答案2，正确。同样，正向能处理())这种"右括号多"的情况：i=0 left=1，i=1 right=1，max=2，i=2 right=2，right 大于 left，触发重置，答案2，也正确。所以双向扫描合在一起，能覆盖所有因为"单边盈余"导致的漏解。

这个解法的复杂度和栈解法一样是 O(n) 时间，但空间复杂度只有 O(1)，只用了两个计数器。它的正确性依赖于一个事实：任何有效括号串，从左往右看任意前缀右括号不超过左括号，从右往左看任意后缀左括号不超过右括号。双向扫描把两个方向的约束都验证一遍，就能保证不被单向盈余骗过去。

4.3 O(1) 空间方案在面试中的定位

这道题在面试中经常作为栈题目的"空间优化追问"出现。面试官看你写完栈解法后，很可能会来一句："能不能不用额外空间？"这时候如果你能直接写出双向计数，并且解释清楚为什么单向不行、两个方向各自能捕获哪种盈余括号，基本就稳了。

但我要提醒一句：不要因为这个解法空间最优，就在面试一开始就抛它。双向计数的推导过程不如栈直观，如果面试官期待的是一步步引导你想到栈，你上来就讲计数法，反而容易显得流程跳跃。稳妥的策略是：先给出最自然的栈解法并解释清楚，主动提一句"这个思路空间是 O(n)，如果面试官希望优化，我还有 O(1) 的双向计数方案"。这种节奏既展示深度，又展示沟通能力，是面试里很加分的处理方式。

5. 三种解法复杂度对比与面试答题策略

5.1 复杂度与代码量对照表

三种解法的复杂度对比如下，我整理成了一张速查表，方便你复习时一眼扫过：

时间复杂度都是 O(n)，因为每个字符都只被常数次操作处理。空间上栈和 DP 都是 O(n)，只有双向计数是 O(1)。有意思的是，代码量最少的栈解法反而不是空间最优，而空间最优的双向计数代码量反而偏大，因为要写两遍几乎一样的循环。这告诉我们一个道理：时间复杂度的极限是 O(n)，但空间复杂度的极限可以压缩到 O(1)，面试时你要根据追问方向决定展示哪个。

还有一个容易被忽略的点：DP 解法虽然代码看起来规整，但它的常数项其实比栈要大，因为每个字符判断的 if 分支更多，而且 dp 数组的随机访问在内存不友好时会慢一些。不过对于 n=3×10⁴ 这个量级，三种解法耗时都在毫秒级，肉眼根本看不出差别。刷题阶段不要纠结微秒级的性能差异，重点是把每种解法的思想吃透。

5.2 不同基础选手的答题顺序建议

如果你是刚开始刷力扣热题100的新手，我的建议是只盯栈解法。原因有三个：第一，栈解法思路直白，和括号匹配的基础题衔接紧密，几乎不需要额外推导；第二，代码只有15行左右，出 bug 的概率最小，手写代码时最稳；第三，它能直接在 O(n) 时间内解决问题，面试已经合格。把栈解法练到能闭着眼睛写出来，包括哨兵 -1 的细节，这一题就算过关了。

如果你已经有了一定刷题量，目标是系统性提升，那就把三种解法都吃透，并且重点放在 DP 和双向计数上。DP 能让你训练"以 i 结尾"这类子串问题的通用建模能力，双向计数能让你体会"贪心 + 方向修正"的思维范式。这两种思维在其它题目里会反复出现，比如接雨水、最长回文子串、盛最多水的容器，都有它们的影子。

如果是面试冲刺阶段，我建议你在纸上把三种解法的思路纲要各写一遍，练习用30秒讲清每一种的核心理由。面试官问"还有别的方法吗"时，你可以先说 DP，再说 O(1) 空间，展示完整的思考链条。这个过程本身就是算法思维升华的过程，很多人刷了几百题但面试表现一般，差别不在于代码能力，而在于能不能把思路组织成有层次的表达。

6. 刷题实战：高频报错与调试排查经验

6.1 高频错误速查表

这道题我刷了三遍，也在面试中面过别人，发现错误出现的位置高度集中。我把常见问题整理成了一张速查表：

你如果有哪一项中了，先别急着抄答案，回到代码里定位是哪个分支漏了。这道题错误高度集中，说明它的正确性对细节极度敏感，而这正是面试官喜欢拿来考人的原因。

调试的时候我强烈建议用 IDE 的 Debugger 而不是 System.out 打点。在栈解法里，逐步查看每次 push、pop 后栈的内容；在 DP 解法里，观察 dp 数组从0到 n 的变化过程。特别是 DP 的第二种转移，你肉眼很难直接看出i - dp[i-1] - 1到底指向哪，IDE 里把这一步的每个变量都展开看一遍，瞬间就通了。

6.2 测试用例设计与调试技巧

面试手写代码时，最忌讳写完之后直接交卷说"写完了"。我见过很多候选人逻辑没问题，但边界用例一测就挂。这道题我建议你至少在纸上测这几组用例：

• ""：空串，答案0
• "("、")"：单个括号，答案0
• "()"：简单配对，答案2
• "(()"：左盈余，答案2
• "())"：右盈余，答案2
• "()()"：连续平级，答案4
• "(())"：嵌套，答案4
• "(()())"：嵌套加平级的混合，答案6
• ")()())"：力扣官方示例，答案4
• "((()))"：三层嵌套，答案6

我自己的经验是，把"(()"和"())"这一对用例放在最前面测，因为它们是"单方向盈余"的代表，一次能同时验证正向和反向逻辑。刷题时如果这组用例过了，再补一个混合的")()())"，基本就能覆盖九成错误。如果用了 DP 解法，再多测一个"(()())"，专门验证第二种转移和边界保护。

还有一个工程上的小细节：力扣的环境里字符串用的是 Unicode，题目保证只有半角英文括号，但如果你从本地文件或终端粘贴测试用例，很可能混入全角括号（）或者不可见空格，这时 charAt 拿到的字符不等于(，代码会安静地跳过，输出结果就错了。遇到"答案莫名小"的时候，先检查输入字符串是不是干净。

6.3 变体题与扩展思考

这道题的变体非常多，在面试中经常被改装。最常见的变体是要求输出最长有效括号子串本身，而不仅仅是长度。解法需要额外记录最大长度对应的起始位置，当max被更新时，同步把起点设为i - max + 1（以栈解法为例），最后用substring截取即可。这个改动很小，但能帮你把"长度计算"和"区间定位"建立联系，我建议你花10分钟改一版。

第二个变体是把括号类型扩成三种，像力扣20题有效括号那样，涉及()[]{}的匹配。这时 DP 和双向计数就不好使了，因为配对关系从"一种符号"变成了"三种符号"，只能靠栈，而且判断条件里要检查栈顶是否是对应的左括号。从这个变体能看出，栈解法的可扩展性是最强的。

第三个变体是"最长有效括号子序列"，即允许跳过字符。这个反而简单很多，答案就是2 * min(left总数量, right总数量)，只需要统计总括号数，不需要任何复杂算法。很多面试官故意先问子序列版本让你放松警惕，再把条件收紧成子串，考察你能否意识到"连续"带来的难度差异。你如果每次都能主动指出这两个问题的本质区别，会给面试官留下很好的印象。

7. 算法思维沉淀：从一道括号题看套路体系

7.1 栈类题型的识别信号

刷题量上来之后你就会发现，栈不是为这道题量身定做的，而是一类问题的通用工具。识别信号有三个：需要处理"最近配对"、需要处理"抵消关系"、需要处理"回退到最近状态"。括号匹配、表达式求值、函数调用栈、浏览器后退按钮，全是这个套路。

这道题教给我们的栈技巧有两个值得沉淀：一是用哨兵元素（-1）避免空栈时的特判，这个技巧在"柱状图中最大的矩形"里也用得到；二是栈里存下标而不是值，让栈从一个数据结构变成"位置索引的追踪器"，遇到需要计算区间长度的问题，优先考虑存储下标。有了这两个意识，栈解法就不再是背代码，而是遇到问题时的自然条件反射。

7.2 "以 i 结尾" DP 套路的延伸

dp[i]表示以 i 结尾的某种状态，这是子串类动态规划最强的套路之一。最长有效括号、最长回文子串、最长递增子序列（严格说那是以 i 结束的最长递增子序列）、最大子数组和，全都是同一个模板：定义以 i 结尾的状态，然后根据当前位置和前一个位置的关系做转移。

这个套路的核心理解方式是：当你处理到第 i 个位置时，不要去想从某个起点开始的整个区间，而是只去想"以 i 结尾这一段怎么接上之前的结果"。就像搭积木，每次只看最后一块积木怎么放上去，而不是重新搭一整面墙。如果你能从这个角度理解 DP，看到"最长 xx 子串"这类题的第一反应就不会是枚举所有子串，而是想状态定义。

7.3 复盘方法：一道题沉淀三类解法

最后聊聊复盘。很多人刷题是"AC了就算过"，今天写完明天忘，我觉得是因为少了"解法对比"这一步。我的习惯是刷完一道题之后，强制自己回答三个问题：这道题的最优时间复杂度和空间复杂度是多少？除了标准解法，还有没有其它角度？哪种解法最适合在面试中引导式讲出来？

对最长有效括号这道题，三个问题的答案分别是：最优时间 O(n)，最优空间 O(1)；除了栈还有 DP 和双向计数；面试讲解首选栈，优化追问再上 DP 或者双向计数。每次复盘都这样过一遍，你的算法思维才会形成体系，而不是散成一堆孤立题解。一道好题的价值不在于AC时的爽快，而在于你从它身上提炼出的那几个"可迁移的思维锚点"。

回到题目本身，(())、()()、(()())这些用例的答案我都亲手推过，3×10⁴ 的长度限制也实测过三种解法在毫秒级完成。做题时最让我意外的不是解法有多精妙，而是最简单的计数思想加上反向扫描，居然能达到和 DP 一样的效果，有的题就是这样，绕了一大圈，真正的钥匙往往藏在最朴素的角度里，但只有你把所有解法都走过一遍之后，才看得见它。