刷力扣hot100的时候很多人卡在第90题“最长有效括号”上久久过不去。这道题表面上是“括号匹配”但真正做起来会发现栈、动态规划、双指针三种主流解法各有各的坑尤其是动态规划的状态转移第一次接触很容易绕晕。我最早做这道题时第一版代码用计数法直接跑挂了后来把三种解法全部吃透才发现这道题值得反复刷它对“子串连续性和括号匹配规则”的考察非常刁钻。这篇文章我就把最长有效括号从题目理解、三种解法的推导过程到面试踩坑点一次讲透适合正在刷力扣hot100、备战算法面试的读者。1. 题目意图与第一直觉陷阱1.1 什么才是“有效的括号子串”题目给一个只包含左括号(和右括号)的字符串s要求返回最长有效括号子串的长度。注意“子串”这两个字它意味着我们找的必须是一段连续的字符区间不是“子序列”。换句话说从整个字符串里抠出来的这段内容必须能完全正确配对并且前后不能有多余的无法配对的括号混在中间。举个例子输入s (()整个字符串从左到右是“左、左、右”其中第 2 和第 3 个字符组成()长度是 2所以答案是 2而不是 3。输入s )()())从下标 1 到 4 的子串是()()长度为 4所以答案是 4。输入s ()(())整个字符串都能正确配对长度是 6。有效括号的严格定义是从左往右扫描任意位置时右括号数量不能超过左括号数量并且最终左右数量相等。这个规则看起来很基础但真到写代码时很多人会忽略“任意前缀”这个前提。这也是为什么后面栈解法要把每个下标都处理清楚。1.2 常见的错误直觉我第一次做这道题时第一反应是开两个计数器遇到左括号加一遇到右括号减一当计数器归零的时候更新答案。这个思路对()()这类字符串是有效的但对()(()就会算错。分析一下s ()(()如果只统计左右括号数量从左到右下标 0(计数 1下标 1)计数 0此时更新长度为 2下标 2(计数 1下标 3(计数 2下标 4)计数 1此时计数不等于 0不更新。这样得到答案 2好像没问题。但换一个例子s (()()总数左右都是 2计数器在扫描到下标 3 时归零得到长度 4而实际最长有效括号子串只有 2或者两个相邻的()其中一段长度也为 2因为下标 0 这个左括号在计数归零时并不属于任何有效子串。这种靠总数平衡来判断的方式在“括号配对成对但中间有缺口”的情况下一定会出错。所以这道题不能靠简单的计数必须真正模拟“哪一段连续可匹配”。2. 辅助栈解法最直观但不无脑2.1 核心思路栈底哨兵法栈解法的核心逻辑其实一句话就能说清用栈来记住“还没被匹配的左括号下标”同时用栈底的一个“哨兵下标”来标记当前有效子串的起点前一位。为什么用栈因为括号匹配天然具备“后进先出”的特性遇到一个右括号时它应该和最近一个还没匹配的左括号配对这正是栈擅长的操作。如果只用计数器一旦出现交错匹配如()(())很难知道当前右括号对应的是哪一个左括号也就难以计算中间的长度。具体做法初始化栈stack [-1]这个-1就是哨兵。它表示“在当前有效子串开始之前的位置是 -1”这样当第一个字符就能匹配时计算长度很方便。遍历字符串的每个字符和下标遇到左括号(把当前下标压入栈遇到右括号)先从栈里弹出一个元素这个元素可能是左括号的下标也可能是哨兵弹出后如果栈不为空说明找到了一个有效匹配用当前下标减去栈顶元素得到一个候选长度更新最大值弹出后如果栈为空说明这个右括号没有匹配的左括号它是一个“孤立右括号”。此时把它自己的下标压入栈作为新的哨兵。这里最容易忽略的细节是为什么孤立右括号要作为新哨兵因为一个无法匹配的右括号会把字符串切成两半之后所有有效子串都不可能跨过这个右括号。新哨兵的意义就是“下一段有效子串的起点前一位”这样之后计算长度时自然会把这段孤立右括号隔离在外。2.2 代码实现与易错点栈解法的时间复杂度是 O(n)空间复杂度是 O(n)代码非常短def longestValidParentheses(s: str) - int: stack [-1] # 栈底哨兵 max_len 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: # 右括号无法匹配成为新的哨兵 stack.append(i) else: # 栈顶元素是当前右括号左侧最近的未匹配下标 max_len max(max_len, i - stack[-1]) return max_len这个写法我实测下来比“栈里存左括号计数”的方式稳定很多。存下标的优势在于当出现合法匹配时i - stack[-1]能直接算出这段有效括号的长度不需要额外维护计数器。写这段代码时最容易踩的坑有三个弹出后别急着更新答案。要先判断栈是否为空为空说明这个右括号没有配对成功需要先入栈。哨兵初始值别设为 0。如果初始栈是[0]当字符串以左括号开头时0会被当作一个普通左括号处理如果初始栈是[]第一个右括号一旦弹出就会出现空栈没法正确标记新的起点。用[-1]是最自然的它能保证“第一个字符配对成功时长度 1 - (-1) 2”。更新长度用当前下标减栈顶不要用弹出元素的下标去减。因为弹出元素可能是中间某段已匹配完的内容真正的有效段终点是当前右括号。我自己的经验是栈解法优点是思路直、不容易写错缺点是空间复杂度是 O(n)而且面试官常会追问“能不能优化到 O(1) 空间”所以只掌握这一种解法是不够的。3. 动态规划这类题真正的分水岭3.1 状态定义与两个转移方向动态规划解法是这道题的精髓也是很多人的痛点。很多人不理解为什么需要dp[i]以及两个转移公式是怎么推出来的。状态定义dp[i]表示以字符串第 i 个字符结尾的最长有效括号子串长度。注意“以 i 结尾”意味着这段子串必须包含s[i]且以s[i]结尾这样定义是为了方便利用之前已经算好的状态。如果s[i] (以左括号结尾一定不可能形成有效括号子串所以dp[i] 0。如果s[i] )需要分两种情况情况一s[i-1] (也就是当前右括号正好和前面相邻的左括号配对成()。那么以i结尾的最长有效子串至少是 2再加上i-2位置之前已经形成的最长有效子串长度dp[i] (dp[i-2] if i 2 else 0) 2这个式子简单但要注意i-2可能越界越界时按 0 处理。情况二s[i-1] )也就是说前一个位置已经是一个右括号。如果以i-1结尾存在一个有效子串长度为dp[i-1]那么当前右括号s[i]想要配对必须去找这个有效子串前面那个字符的下标即j i - dp[i-1] - 1。如果j 0且s[j] (说明当前右括号可以和s[j]配对此时dp[i] dp[i-1] 2 (dp[j-1] if j 1 else 0)这里dp[j-1]表示s[j]这个左括号之前已经匹配好的那段有效括号的长度。为什么需要加dp[j-1]因为当前右括号配对的左括号往前可能还紧挨着一整段有效括号。例如()(())最后一个右括号配对时它配对的是下标 2 的左括号而该左括号前面还有dp[1] 2的()所以最终长度是 2 4 6。3.2 手动推导一类关键样例光看公式容易晕我用手动推导带着大家走一遍经典用例)()())这道用例正好能覆盖两种转移情况。字符串下标下标012345字符)()())初始化dp全为 0答案res 0。i 0字符是)s[-1]不存在走情况二时j 0 - 0 - 1 -1越界所以dp[0] 0。i 1字符是(dp[1] 0。i 2字符是)s[1] (走情况一dp[2] dp[0] 2 2。此时最长长度为 2。i 3字符是(dp[3] 0。i 4字符是)s[3] (走情况一dp[4] dp[2] 2 4。此时最长长度为 4。i 5字符是)s[4] )说明要走情况二。dp[4] 4所以j 5 - 4 - 1 0s[0] )不是左括号不满足配对条件因此dp[5] 0。最终res 4正确。再看一个容易出错的例子(()下标012字符(()i 0dp[0] 0。i 1dp[1] 0。i 2字符是)s[1] (走情况一dp[2] dp[0] 2 2。答案也是 2正确。动态规划解法的完整代码def longestValidParentheses(s: str) - int: n len(s) dp [0] * n res 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: # 情况二s[i-1] ) j i - dp[i - 1] - 1 if j 0 and s[j] (: dp[i] dp[i - 1] 2 (dp[j - 1] if j 1 else 0) res max(res, dp[i]) return res写 DP 时最容易犯的错是忘记处理越界。比如i - 2、j - 1、j 0这几个边界条件漏掉任何一个都可能出现数组越界或者漏算。另一个容易错的地方是dp[i]只有在当前字符是)时才可能大于 0所以状态转移只用考虑右括号。动态规划的好处是写出了dp数组后整个匹配过程一目了然面试时讲推导过程会给面试官留下好印象。缺点是对初学者来说情况二的跳跃下标比较抽象需要多画图理解。4. 双指针O(1)空间解法的巧妙设计4.1 两轮遍历的必要性如果面试官继续追问“空间复杂度能优化到 O(1) 吗”那就需要拿出双指针解法。这个解法的核心是用两个计数器left和right分别记录当前扫描到的左括号数量和右括号数量然后分从左到右、从右到左两轮遍历。先说为什么要两轮遍历。如果只从左往右扫一遍遇到(()时会失败扫描完整个字符串left 2right 1left ! right永远没有机会更新答案。但事实上这个字符串里是存在长度为 2 的有效子串的只是它在整个字符串中不满足左右括号数量相等所以在一次从左到右的扫描里被漏掉了。原因在于从左往右扫描时遇到的是“右括号比左括号多”的情况就表示当前这段不匹配可以重置但遇到“左括号比右括号多”的情况可能到字符串结尾时左括号仍然多出来导致没触发更新。为了处理这种“左括号过多”的情形就需要再从右往左扫一遍。反向扫描时遇到“左括号比右括号多”就重置这样就能覆盖(()这类字符串。听起来有点绕用一句话总结从左往右解决右括号过剩从右往左解决左括号过剩。括号匹配的合法性在任何前缀都要满足右括号数不超过左括号数因此两轮遍历可以覆盖所有合法子串。4.2 代码对照与细节验证双指针解法的代码def longestValidParentheses(s: str) - int: left right max_len 0 # 从左到右处理右括号过多导致不匹配的情况 for ch in s: if ch (: left 1 else: right 1 if left right: max_len max(max_len, left 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: max_len max(max_len, left right) elif left right: left right 0 return max_len这段代码的细节值得逐条说。第一轮从左到右遇到right left时说明出现了无法匹配的右括号此时无论left和right是多少当前这一段都不可能再延续下去所以全部清零重新开始扫描新的子串。例如)()())下标 0 的右括号就会触发一次重置。第二轮从右到左对称地处理left right的情况。为什么反向时是“左括号过多”才重置因为从右往左看右括号相当于“正向期望的左括号”反过来扫描时左括号过多意味着正向扫描中的“未闭合的左括号”多于匹配它的右括号这段也不合法因此重置。例如(()从右往左扫描下标 2 是)right 1下标 1 是(left 1left right更新长度 2下标 0 是(left 2left right重置。这样长度为 2 就被记录下来了。这个解法的时间复杂度是 O(n)空间复杂度 O(1)代码更短但理解起来比栈解法抽象。不过一旦理解了“双向计数”的设计逻辑面试现场也能临场推导出来不需要硬背。5. 刷题与面试场景下的解题策略5.1 三种解法的选择逻辑面试中面对“最长有效括号”这道题思路应该是有层次的先给出栈解法因为最容易讲清楚再给出动态规划解法展示状态设计能力最后补充双指针 O(1) 空间解法体现优化意识。不要一上来就甩最优解面试官通常更看重分析过程。我把三种解法的核心信息整理成一张表方便对照解法时间复杂度空间复杂度核心思想适合场景辅助栈O(n)O(n)栈存下标 哨兵思路直观适合第一反应和笔试快速 AC动态规划O(n)O(n)dp[i] 表示以 i 结尾的有效长度展示状态转移能力边界条件需要细心双指针O(n)O(1)两轮扫描 计数追求空间最优面试加分项如果你刷题时间紧张我个人的建议是优先背熟栈解法因为它代码短、不容易写错笔试时能快速通过但如果目标是面试最好把 DP 和双指针都理解到位。面试官一追问“能不能不用额外空间”是很常见的情况如果你当场卡住对比就很减分。另外一个实用技巧这道题可以用“以怎样的前缀顺序扫描”来辅助记忆双指针解法。第一轮从左到右处理右括号过多第二轮从右到左处理左括号过多两次扫描都只在left right时更新答案。记住“双向扫”这个关键词代码基本不会写错。5.2 一套通用的测试用例与自查习惯写完代码后建议立刻用下面这一组用例自测。这道题的边界情况很多不测试很容易漏算s 答案是 0。s (答案是 0。s )答案是 0。s ()答案是 2。s (()答案是 2。s )()())答案是 4。s ()(())答案是 6。s ((()))答案是 6。s (()())答案是 6。尤其要注意(()和)()())这两个例子它们能同时检验栈、DP、双指针三种写法的正确性。我自己调试时曾经因为栈解法初始哨兵写错导致(()算成了 4后来用这组用例一跑就暴露了。如果你想把题目再延伸一下改成“返回最长有效括号子串本身”可以在更新最大长度的同时记住对应的起始下标和结束下标最后切片返回即可。栈解法里这个改造尤其简单当max_len被更新时起点就是stack[-1] 1终点是i把这两个下标记录下来就行。做算法题有时候就是这样一道题的三种解法本身就是一套完整的思维训练从直观的栈模拟到抽象的 DP 状态迁移再从空间上做极致的优化。把这三种解法都吃透以后你会发现括号匹配类的题目虽然变体多但底层逻辑逃不出这几个框架。如果你再遇到力扣上其他跟括号相关的题目比如“有效的括号”“括号生成”分析起来会顺手很多。