1. 题目拆解Hard题里的最长连续到底在考什么LeetCode 32 最长有效括号Longest Valid Parentheses我在刷题列表里见过它太多次了。题目本身一句话就能说完给定一个只包含 ( 和 ) 的字符串找出最长的有效且连续的括号子串长度。比如输入(()答案是 2因为中间那块()长度是 2而整个字符串并不是合法的括号串输入)()())答案是 4因为中间有一段()()是连续的合法括号子串。题目还有个限制空字符串的长度是 0。我第一次做这题的时候第一反应是这不就是第 20 题有效的括号吗用栈扫一遍不就完了。但真正动手之后才发现完全不是一回事。第 20 题只要求判断整个字符串是不是合法的括号序列遇到不匹配的字符直接返回 false 就结束了这道题要求的是从一个可能存在多处断裂、多段合法片段的字符串里找出最长的那一段。它不关心全局是否合法只关心局部连续匹配的最大长度。用生活里的话说第 20 题是检查一篇作文有没有语法错误这一题是在一篇满是病句的作文里找最长的一句完整通顺的话。题目里最要命的是连续两个字。连续意味着你不能像求子序列那样跳过中间不合法的字符一旦中间被一个孤立的括号隔断前面的长度就得全部作废。比如())()前面()是合法的中间一个单独的右括号把整个区间切断了后面()又从头开始算所以最长只能是 2不是把前后拼起来的 4。这一点很多人写暴力枚举的时候就会踩进去因为只看左右括号数量相等还不够还要保证任意前缀中左括号数量不小于右括号数量。换句话说)(这种左右数量相等的子串实际上根本不是一个合法括号子串。这道题虽然标着 Hard但核心考点非常集中字符串线性扫描、栈的使用、动态规划的状态设计以及如何用常数空间解决区间最值问题。常见的三种线性解法分别是动态规划、栈、左右双向扫描。我认为把这三条路都走一遍比单纯背代码有价值得多因为它们分别对应了状态定义数据结构选型空间优化三类不同的思考方式。2. 动态规划解法用dp[i]锁定以i结尾这个关键状态2.1 状态定义为什么必须带结尾先说结论dp[i]表示以字符s[i]作为右端点时能形成的最长有效括号子串的长度。这个以 i 结尾是整道题 DP 思路的命门。为什么不定义成从 0 到 i 的最长有效括号长度因为括号匹配这件事有强烈的方向性。一个有效括号子串一旦闭合它右侧紧挨着的下一个字符能不能继续参与构成更长的子串取决于它左侧紧贴的那段是否已经闭合完整。定义必须以某个位置为结尾才能把这一段已经闭合、长度为多少的信息准确传给后面的字符。这其实和最大子数组和的 DP 思路同源你想求全局最值但状态必须落在局部端点否则没办法递推。如果s[i]本身是(那以它结尾的合法子串长度一定是 0因为没有一个合法括号子串会以一个未闭合的左括号作为右端点。这个处理看起来简单但实际上帮 DP 自动做了断点隔离中间只要出现任何一个不匹配的位置对应位置的 dp 就是 0后续拼接自然就从 0 开始不会跨过断点。2.2 两类转移与下标边界陷阱真正需要分析的是s[i] )的情况。此时 i 前一个字符是谁决定了两种完全不同的转移路径。第一种情况s[i-1] (。这两个字符直接配对基础长度为 2如果s[i-2]还能作为某个有效子串的右端点前面的部分也要接上所以dp[i] dp[i-2] 2当 i-2 存在时否则就只是 2。举例来说()()在 i3 这个右括号的位置dp[3] dp[1] 2 2 2 4它把前一段()和后面新配对的()拼成了完整的一段。第二种情况s[i-1] )说明 i 左侧紧贴着一个已经闭合好的有效子串这个子串的长度是dp[i-1]。想让s[i]这个右括号也能加入进来就必须在它左侧找到对应的左括号。具体位置就是j i - dp[i-1] - 1。如果j 0且s[j] (那么s[j]和s[i]形成一对新括号把中间那段已经有效的子串包在了里面。此时dp[i] dp[i-1] 2。但还没结束s[j]左边可能还接着一段有效子串也就是dp[j-1]也需要接上所以再补dp[i] dp[j-1]当 j-1 存在时。这里最容易翻车的点全在下标边界。写代码的时候i - 2 0、j 0、j - 1 0三个条件少一个都有可能越界或者少算一段。很多题解里喜欢把dp[-1]当作 0 来处理但 Python 里列表索引-1会直接取最后一个元素这是个大坑所以我习惯在代码里用条件判断把边界挡掉宁可多写几个 if也不依赖语言特性。2.3 一步步运行()(())从dp数组看匹配过程直接看代码会更清楚class Solution: def longestValidParentheses(self, s: str) - int: n len(s) if n 0: return 0 dp [0] * n ans 0 for i in range(1, n): if s[i] ): if s[i - 1] (: dp[i] (dp[i - 2] if i 2 else 0) 2 else: j i - dp[i - 1] - 1 if j 0 and s[j] (: dp[i] dp[i - 1] 2 if j - 1 0: dp[i] dp[j - 1] ans max(ans, dp[i]) return ans拿()(())手动跑一遍。这个例子特别适合理解嵌套和并列两种结构同时出现时DP 是怎么工作的。i1s[1] 是)s[0] 是(直接配一对dp[1] 2。i2 和 i3 都是左括号dp 都为 0。i4s[4] 是)s[3] 是(属于第一种情况dp[4] dp[2] 2 2此时()这一对闭合。i5s[5] 是)s[4] 是)走第二种情况。dp[4] 2所以j 5 - 2 - 1 2而s[2]正好是(于是dp[5] dp[4] 2 4。再看j - 1 1dp[1] 2说明这个左括号前面还接着一段()把两段一起拼上最终dp[5] 6。整个过程能看到一个很漂亮的特性DP 天然处理了并列拼接和嵌套包裹两种结构。dp[i-1]负责传递右侧已经闭合的长度dp[j-1]负责传递左侧已经闭合的长度中间通过一对新括号把它们连起来。这也是为什么我说这道题适合用来理解状态设计要带端点这个思路比死记转移方程有意义得多。3. 栈解法哨兵元素-1为什么能一招定乾坤3.1 栈内存下标而不是括号本质是把断点留在栈里很多人从第 20 题走过来很自然地想在栈里存字符(或)。但这道题里栈里存的下标才是关键。为什么因为最终要求的是长度而长度必须由位置相减得到。你只存一个字符根本不知道这一对括号在字符串里的具体位置也就无法算出从哪到哪是有效的。栈的语义其实很单纯栈底到栈顶存的是到目前为止那些还没被匹配掉的左括号的下标以及历史上曾经出现的、不能再继续参与匹配的断点下标。每当我们用一个右括号弹出栈顶左括号时新的栈顶天然就是当前有效区间左侧边界的前一个位置。于是当前有效区间的长度就是当前下标 - 栈顶下标。这里的核心思想不是匹配本身而是用栈维护最后一个失效位置这个位置就是计算区间长度的锚点。我可以打个比方栈里的元素像一串打了结的绳子上的绳结。每遇到一个无法匹配的字符就相当于绳子在这里打了个死结后面无论绳子怎么绕都不可能跨过这个结去和前面的部分组成完整的一段。栈顶的索引就是这个死结的位置。3.2 代码实现与一条公式 i - stack[-1]直接看代码class Solution: def longestValidParentheses(self, s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans这段代码短到有点不可思议但每一行都有讲究。初始化先压一个-1它的意思是整个字符串开始位置的前一位。为什么需要这个哨兵考虑最简单的情况()i0 遇到左括号压入 0i1 遇到右括号弹出 0。此时栈如果只有-1那i - stack[-1] 1 - (-1) 2正确算出长度 2。如果没有这个 -1遇到第一个有效子串时栈会变成空你还得特判如果栈空就说明当前是一个完整串逻辑分支会多出一堆。遇到右括号时无论栈里是什么先无条件pop()。这一步的目的是把可能的匹配对象或哨兵弹出去。如果弹出之后栈空了说明这个右括号没能找到配对的左括号它自己成为一个新的断点所以要把当前下标i压回去作为后续所有区间的新的起点基准。如果弹出之后栈还有元素说明栈顶就是当前有效区间左边界的前一个位置直接相减更新答案。用)()())走一遍初始栈[-1]。i0 是)pop 掉 -1栈空压入 0此时栈[0]意思是位置 0 是一个孤立右括号后面任何合法区间都不可能越过它。i1 是(压入 1栈[0,1]。i2 是)pop 掉 1栈顶 0 还在长度 2 - 0 2。i3 压入 3i4 是)pop 3栈顶还是 0长度 4 - 0 4。i5 是)pop 0栈空压入 5。最终答案 4。整个过程里位置 0 的孤立右括号一直充当断点基准一直没被替代直到它自己被后续的右括号弹掉。3.3 孤立右括号被pop后为什么要重新入场作哨兵这是一个我当年想了很久的细节为什么pop()之后如果栈空了要把当前右括号下标i再压回去这个右括号不是已经确定无法匹配了吗压回去它以后还会被谁弹出来答案在于它不需要再扮演等待匹配的左括号它要扮演的是断点本身。假设字符串是)()i0 的右括号把 -1 弹掉栈空如果我们不压 0 进去那么 i2 的右括号在 pop 掉 i1 的左括号后栈就空了此时长度怎么算都算不对但如果压了 0i2 时 pop 掉 1 后栈顶是 0长度 2 - 0 2正对应位置 1 和 2 组成的()。换句话说孤立右括号把字符串切成了两半它自己就是后半段的起点前一位所有后续有效区间的长度都要从它后面开始算。这个设计直接把断点检测和长度计算统一成了一条规则栈里永远保证至少有一个元素这个元素要么是未匹配的左括号下标要么是断点下标。栈顶元素和当前右括号下标的差值就是跨过断点之后、从断点右侧到现在为止能形成的最大有效长度。理解了这个之后再看那行if not stack: stack.append(i)就不是死记硬背而是重新立一个断点坐标。4. 常数空间的左右双向扫描O(1)内存破解Hard4.1 为什么单向计数会漏解以(()为例栈解法的时间是 O(n)空间也是 O(n)。如果面试官追问一句能不能把空间压到 O(1)就需要拿出左右双向扫描这个解法。它的思路比 DP 和栈都更贴近括号匹配的计数本质。先说一个反直觉的事实很多有效括号子串用简单的左括号加一、右括号减一从左到右扫一遍是找不出来的。看(()从左往右数位置 0 左括号计数 1位置 1 左括号计数 2位置 2 右括号计数变成 1。整个过程计数始终大于 0从来没有出现左右数量相等的瞬间所以如果只在计数归零时更新答案从左到右就什么都得不到。但答案明明是 2也就是位置 1 和 2 组成的()。问题出在计数器的起点。从左往右时我们默认从位置 0 开始累积可一旦前面多出来一个无法闭合的左括号这个多余的左括号会把后续所有的平衡点都顶高导致即使出现了合法片段计数也碰不到零。这里的本质是从左向右只能发现那些左括号最终被右括号抵消干净的子串却漏掉了开头被多余左括号占据、但后面依然有合法片段的情况。4.2 左右双向扫描的计数规则双向扫描的核心思路是既然从左往右会被多余的左括号干扰那就再从右往左扫一遍。右边扫描时多余的右括号会被视为需要重置的断点而左括号过多时同样需要重置逻辑完全镜像。具体规则分两趟。第一趟从左往右维护 left 和 right 两个计数器遇到(让 left 加一遇到)让 right 加一。当 left 等于 right 时说明当前累计的这段左右数量相等是一个候选合法区间用2 * right更新答案。当 right 大于 left 时说明右括号过多从当前起点开始不可能再构成合法区间把两个计数器清零重来。第二趟从右往左规则镜像同样遇到(让 left 加一遇到)让 right 加一平衡时更新答案但当 left 大于 right 时清零重来。代码相当短class Solution: def longestValidParentheses(self, s: str) - int: ans 0 left right 0 for ch in s: if ch (: left 1 else: right 1 if left right: ans max(ans, 2 * right) elif right left: left right 0 left right 0 for ch in reversed(s): if ch (: left 1 else: right 1 if left right: ans max(ans, 2 * left) elif left right: left right 0 return ans第二趟更新答案时用2 * left还是2 * right其实无所谓因为进入平衡分支时两者相等。真正的考点在重置条件第一趟是right left重置第二趟是left right重置方向正好相反。一旦想当然地把第二趟也写成right left一些用例就会给出错误答案。4.3 第二遍遍历里的一个隐藏重置坑这个坑我印象很深。拿())()(来测试这个字符串的最长有效括号长度是 2因为只有两个单独的()片段。但从右往左扫的时候如果第二趟的重置条件写反很容易算出 6。为什么因为这个字符串的左右括号总数都是 3如果不做任何重置两趟扫描甚至可能在某个时刻错误地认为整个字符串是平衡的。正确的第二趟扫描过程是这样的从右往左遇到第一个字符是(left 变成 1right 是 0此时left right触发重置计数器清零。如果不触发这个重置窗口就会把这个孤立左括号一直带着后面再遇到几个括号把计数补平就可能误以为存在一段很长的合法区间。这种错误在样例不多的测试里很难发现因为常规样例往往左右括号配得比较整齐。这告诉我们一个道理双向扫描的本质不是找平衡点而是同时用两趟扫描分别覆盖不同方向上的非法前缀。第一趟覆盖了右括号导致的前缀失效第二趟覆盖了左括号导致的前缀失效。两趟合在一起才能保证所有可能的有效区间都能被某个方向的扫描发现。所以第二趟的重置条件不是照抄第一趟而是要根据扫描方向镜像翻转。5. 边界用例与坑位盘点把三种解法放在同一个测试台5.1 七个必测样例的手算对照算法题最怕的不是主流程写错而是边界和特殊输入把代码击穿。我建议正式提交前至少把这几个用例全部过一遍它们基本覆盖了这道题的所有隐蔽分支。输入期望输出最容易出错的地方0空串时 dp 数组为空for 循环不执行(0单个左括号永远无法闭合()2栈解法里哨兵 -1 的正确性(()2第一趟从右到左扫描能否补回长度)()())4孤立右括号作为断点分隔两个合法片段()(())6DP 中dp[j-1]拼接并列段())()(2双向扫描第二趟重置方向写错会误算成 6(()())6嵌套与并列同时存在时的整体闭合这里我特别想强调()(())这个用例。它外层看是一段()加上一段(())的并列结构所以正确答案是 6。用 DP 做的时候i5 那个位置的右括号不仅要把内部的(())包进来还要把左侧已经闭合的()也接上如果你漏写了dp[j-1]的拼接答案就会停在 4。这个用例能很好地检验状态转移是否写完整。5.2 为什么这三种解法都能稳定O(n)暴力为什么不行题目给出的字符串长度上限通常是 3 万左右。如果上来就写暴力枚举需要枚举所有子串数量是 O(n^2)。就算用同时维护左右括号计数的优化把判断合法子串压缩到 O(1)9 亿次操作在大多数平台上依然会超时。而且暴力枚举还有一个隐蔽问题只统计左右括号数量相等还不够还要验证任意前缀左括号不少于右括号这个验证在枚举时非常容易写漏。所以在这道题里线性解法不是可选项而是唯一能稳定落地的方案。三种线性解法的时间和空间对比如下解法时间复杂度空间复杂度核心依赖动态规划O(n)O(n)dp 数组保存以每个位置结尾的最大长度栈O(n)O(n)栈保存下标与断点位置双向扫描O(n)O(1)左右两个计数器两趟遍历如果面试官问能不能不用额外数组栈解法其实也符合不用数组的要求因为栈是线性表面试时聊到这里会被继续追问能不能连栈都不用双向扫描就是收尾答案。我个人推荐把三种解法的复杂度背熟现场推导顺序一般是先答栈再答双向扫描最后按需补充 DP。5.3 我在实际提交中踩到的下标越界与状态没清零写 DP 解法时我吃过两次亏。第一次是忘记了i - 2 0的判断导致()这种两个字符的输入直接访问dp[-1]在 Python 里不会报错但会拿到最后一个元素结果完全错误。第二次是在第二种转移里判断j 0 and s[j] (之后继续访问dp[j-1]时忘了检查j - 1 0结果在()这类简单用例上又翻车。下标问题在 DP 题里几乎不可避免我的经验是写完代码后专门拿长度 0、1、2 的输入各跑一遍再跑一个嵌套一个并列的复杂用例基本能把越界和漏拼接都测出来。写双向扫描时我的问题则是另外一个类型第二趟重置条件写反。第一趟是right left重置第二趟我习惯性复制过来改成right left结果跑())()(直接输出 6。排查了很久才发现第二趟应该用left right。后来我养成一个习惯每一趟的代码都单独注释上当前重置条件代表哪个方向的非法前缀这样就算复制粘贴也不容易弄混。6. 面试表达与刷题心得从暴力到O(1)的临场节奏6.1 第一反应暴力枚举子串和为什么很快被否定如果在面试现场拿到这题先别急着写最优解把暴力思路说清楚反而显得你思考路径完整。暴力做法是枚举左端点和右端点对每个区间判断是否合法。判断方法很简单维护一个计数器遇到左括号加一遇到右括号减一如果中途计数器变成负数说明右括号太多区间非法如果最终计数器等于零说明合法。枚举所有区间需要 O(n^2)判断合法性又需要 O(n)总复杂度 O(n^3)。就算用增量法把合法性判断降到 O(1)O(n^2) 依然不够看。这个暴力思路的价值在于它天然引出了两个关键观察第一合法的括号区间必然左右数量相等第二中间任何一个前缀如果右括号多了这个区间就必须被切断。这两个观察分别对应了双向扫描和栈解法里的重置思想。所以哪怕暴力不能过题也要能在面试里清晰讲出它为什么慢、慢在哪里。6.2 面试官面前的推导路线先栈再O(1)最后聊DP我的建议是面试时按栈 - 双向扫描 - DP的顺序讲而不是按题解常见顺序从 DP 开始。因为大多数人刚做过第 20 题有效括号从栈入手最自然。先说出如果栈里存下标那么每次匹配成功用当前下标减栈顶下标就是长度配合哨兵 -1 解释为什么第一个合法片段也能算出来这已经是一版正确的 O(n) 解法。接下来面试官大概率会问空间复杂度能不能再省。这时候引出双向扫描从左往右只能对付右括号过多的断点从右往左才能对付左括号过多的断点两趟扫描结合空间变成 O(1)。讲的时候重点强调第二趟的重置条件是镜像的不能照抄第一趟。这里如果能主动举例说明(()是第一趟漏掉、第二趟找回的说服力会很强。如果面试官还想考察状态设计再讲 DP。先定义以 i 结尾的 dp 含义再分s[i-1] (和s[i-1] )两类讨论最后用()(())演示并列拼接。这样三条路都覆盖到了无论是算法能力还是沟通能力都能展示出来。6.3 周赛与日常刷题的一些细节习惯在 LeetCode 热门 100 题和周赛讨论区里最长有效括号经常被当成看起来简单、写起来全是坑的代表。我刷这道题时养成了几个习惯写在这里供大家参考。第一先用暴力代码当裁判。我本地会写一个非常朴素的暴力函数生成几千组随机括号串然后拿三种解法和暴力结果比对。这个做法能非常快地发现双向扫描重置条件写错这类隐蔽问题比我手动构造样例快得多。第二善用答案必然是偶数这条性质自查。最长有效括号子串的长度一定是个偶数如果某个用例跑出来奇数基本可以断定状态转移或者计数器更新有问题。第三提交前把空串、单字符、全左括号、全右括号这四类极短输入先跑一遍这类输入能把索引进界问题一次性暴露出来。这道题我后来在多个刷题群和讨论区里反复看到有人发帖问为什么我栈解法明明看起来没问题答案却不对大部分时候都是因为没有理解断点下标的作用或者把i - stack[-1]误写成了i - stack[-1] 1。后者是另一个常见误区哨兵 -1 代表的是区间起点之前的位置所以不需要加一只有当你存的是区间起始下标本身时才需要加一。理解了哨兵的语义这一行公式就永远不会写错。最后聊点我自己的习惯。我刷这题的时候是先写了暴力校验函数再写三种解法生成几千组随机括号串做暴力比对。随机测试跑了几轮之后双向扫描第二遍的重置条件问题果然被揪出来了。这种拿暴力当裁判的刷题方式比对着样例干想稳得多也更有意思。如果时间充裕我建议你也把三种解法都写一遍再用随机数据互相验证这道题值得这个投入。