刷过算法题的人基本都绕不开这么一道经典题目给定一个只包含左括号和右括号的字符串判断括号是否有效顺便看看最大嵌套深度有多深再找一找最长有效括号子串的长度。一个标题把三个层次全占了从基础的有效性判断到进阶的最大深度统计再到压轴的最长有效括号子串难度和技巧是逐步拉满的。这篇文章就围绕这三个层面逐一拆解把为什么要这么做、怎么做、以及哪里容易踩坑都讲透顺便聊聊这类问题在真实工程里到底有什么用。初看这道题很多人觉得不就是栈吗左括号入栈右括号出栈最后看栈空不空完事。但实际刷题和面试中它延伸出的三个子问题每一个都有不同的写法和隐蔽的坑。哪怕是最简单的有效性判断也有人因为没处理好“只有右括号没有左括号”这种边界条件而翻车。更别说最长的那个子问题暴力解法思路简单但复杂度直接爆炸O(n^3)的写法在稍微长一点的输入下都要卡到怀疑人生而动态规划或栈加索引的做法却能把复杂度压到O(n)完全是两种体验。这篇文章会把三个问题放在一起系统梳理适合刚开始刷题的初学者也适合准备面试想快速复习的人。内容不搞虚的直接给思路、给代码、给复杂度分析再配合一些我在实际跑代码时遇到的反直觉案例。这题无论刷多少遍每次都能看出点新东西尤其是最长有效括号子串解法之巧妙值得反复琢磨。1. 三个问题一条主线括号匹配的底层逻辑先厘清一个最基本的事实括号匹配问题本质上是在处理“对称性”和“最近匹配”的关系。一个左括号要想找到它对应的右括号必须遵循一个隐式的规则——后出现的左括号先被匹配也就是LIFO顺序后进先出。这正是栈这个数据结构的天然特性。所以三个问题其实共用同一条基础逻辑有效性判断所有左括号都能找到对应的右括号且顺序正确。最大深度记录栈中左括号数量的峰值。最长有效子串找出连续一段满足括号匹配规则的最长区间。为什么不用队列因为括号匹配是最近匹配不是先进先出。举一个直观的例子字符串(()())如果你用队列去匹配第一个右括号会被安排去匹配最左边的左括号但真实规则是它应该匹配紧邻自己左边的那个左括号。用栈就非常自然新来的右括号永远和栈顶元素做匹配栈顶就是最近一个还没被匹配的左括号。1.1 从暴力解法看问题的本质先说说暴力法虽然它效率低但对理解问题本质很有帮助。暴力判断有效性很简单从每个位置出发尝试截取子串然后对这个子串做匹配判断。问题是每个子串判断一次是O(n)子串数量是O(n^2)总体就是O(n^3)。字符串长度一上100这个算法基本就跑不动了。暴力法会重复做太多无用功。比如检查子串[i, j]的有效性和检查[i1, j]的有效性两者之间有大量重复计算。这就是“最优子结构”和“重叠子问题”这两个动态规划关键词的由来。如果你只追求“能跑”暴力法当然能跑但如果你想刷题、面试、或者处理真实长文本就要考虑线性解法。1.2 为什么栈能一统天下栈之所以能应对括号匹配的所有变体关键在于它天然维护了“最近未匹配的左括号位置”。有效的时候栈空深度最大的时候栈最高找最长子串的时候用索引在栈里做文章。它就像是给括号文档配了一个“待办事项清单”每遇到一个右括号就从清单里划掉最近的一个左括号如果清单本来就空那就是非法状态。作为对比有些语言的正则表达式也能处理简单括号匹配但正则无法直接处理嵌套深度任意层的情况因为正则表达式本身没有递归能力除非用了递归匹配的扩展语法那又另说。所以栈是这一系列问题是通用且标准的工具。2. 小括号的有效性从基础算法到边界条件的自我修养有效括号的判断是三个问题里最基础的一环但也是陷阱最多的一环。题目标准描述是给定一个只包含(和)的字符串判断它是否有效。有效意味着每个左括号都有一个对应的右括号且左右括号的配对顺序完全正确。2.1 栈解法一看就会一写就废先上最标准的栈解法。遍历字符串的每个字符遇到左括号就入栈遇到右括号如果栈为空说明右括号没有对应的左括号直接返回False如果栈非空就弹出栈顶的一个左括号完成一次配对。遍历结束之后如果栈为空说明所有左括号都被匹配掉了字符串有效如果栈里还有剩余说明有左括号没等到右括号字符串无效。用代码写起来大概是这样的bool isValid(string s) { stackchar st; for (char c : s) { if (c () { st.push(c); } else { // c ) if (st.empty()) return false; st.pop(); } } return st.empty(); }这段代码看着简单但有几个非常容易被忽略的细节。第一如果题目出现在面试里面试官可能会追问除了(和)还有[、]、{、}怎么办这时候字符串变复杂了右括号不仅要求栈里有左括号还要求栈顶的左括号类型与自己匹配。很多人在这个扩展版本上翻车只判断了栈空不空忘了判断栈顶类型是否匹配结果([)]这种明显非法的字符串也能被判断成合法。第二如果输入里混入了空格或者无关字符比如((a)b)这种带字母的情况就需要先做预处理过滤只保留括号字符。在实际的编辑器、编译器场景中你看到的源文本永远不会像刷题那样干净这部分处理得单独写清楚。2.2 计数器法空间复杂度 O(1) 的巧妙替代刷题刷得多的人会知道针对只含一种括号的场景还有另一种更省的写法不借助栈只用一个计数器count。遇到左括号count遇到右括号count--任何时候如果count 0说明右括号比左括号先出现了字符串无效。最后看count 0是否成立。bool isValid(string s) { int count 0; for (char c : s) { if (c () count; else if (--count 0) return false; } return count 0; }这个写法的时间复杂度是O(n)空间复杂度降到了O(1)比栈更省内存。但注意它有一个大前提字符串里只有一种括号。一旦括号种类变多比如([)]计数器法就完全失效因为不同种类的括号不能合并计数。这里我的建议是刷题阶段栈解法必须熟练到闭眼能写因为它是通用方案计数器法可以作为进阶技巧了解面试时如果能主动说出“这只适用于单类型括号”反而会是加分项说明你对方法的适用边界想得清楚。2.3 边界条件与反直觉用例盘点有效性判断的坑通常不在核心逻辑而在边界。我自己调试的时候遇到过这么几个印象深刻的场景空字符串算不算有效按常规定义空字符串是有效的因为没有任何未匹配的括号。字符串)(是无效的因为第一个字符就是右括号直接触发count 0或栈空返回false这个比较直接。字符串()(()是无效的因为最后那个左括号没有匹配栈不为空。字符串())是无效的因为遍历到索引2的右括号时栈已经空了。字符串((()))是有效的而且它的最大深度是3这里就已经牵扯到第二个问题了。这些边界条件单独拎出来看都很简单但合在一起就是要保证你的实现能同时处理“过早出现右括号”“结尾残余左括号”“空串”这三类情况。写代码之前先在脑内跑一遍这三个用例基本能过滤掉绝大多数bug。3. 最大嵌套深度把栈的高度变成答案第二个问题是最大深度。比如字符串((()))的最大深度是3字符串(()())的最大深度是2字符串()(())的最大深度也是2。最大深度的含义就是字符串里最深的括号嵌套层数这实际上是在有效性的基础上再加一个问题遍历过程中栈里最多同时存在几个左括号3.1 一次遍历同时完成有效性和深度统计既然深度就是栈的最大高度那在遍历的同时记录栈的最大size就可以了。核心逻辑和有效性判断完全一致唯一区别是每次入栈之后更新一下当前深度。int maxDepth(string s) { int depth 0, maxDepth 0; for (char c : s) { if (c () { depth; maxDepth max(maxDepth, depth); } else if (c )) { if (depth 0) return -1; // 非法情况可自定义 depth--; } } return depth 0 ? maxDepth : -1; }注意这里我留了一个语义上的小设计如果最终depth不为0说明字符串非法那此时谈最大深度是没有意义的所以返回-1表示出错。面试的时候这种对异常情况的主动处理通常会被视为加分项说明你想的不是“做题”而是“写健壮的代码”。还有一点容易被忽略如果输入的括号字符串可能包含其他字符比如a(b(c)d)那么需要在遍历时跳过非括号字符。当然如果题目明确说了“只包含括号”这步就可以省了。3.2 最大深度在真实场景里有什么用很多人觉得最大深度是个刷题时才有的概念但真到了工程里这个指标特别有用。比如编译器在解析表达式时需要限制嵌套层数防止栈溢出和过深的递归调用又比如一些结构化文本解析器会检查括号嵌套深度超过阈值就报错避免恶意输入导致系统资源耗尽。我在写一个简易表达式求值器时就用到了这个思路先遍历表达式实时统计括号深度一旦深度超过预设上限比如64层直接终止解析并抛出异常。这比让解析器递归到爆栈再报错要优雅得多而且用户能立刻得到清晰的错误信息。3.3 递归解法的脑洞与限制还有一种写法用递归去计算深度。思路是外层括号包裹的字符串其深度等于内部子串深度加1。问题在于如果嵌套深度很大比如10000层递归调用本身会消耗大量函数栈空间容易爆栈。相比之下迭代式的栈解法只需要一个计数器或一个栈对象内存占用是O(n)或者O(1)稳定得多。因此我在工程实践中几乎不会用递归去处理括号深度的问题。这不是说递归不好而是根本场景不匹配括号解析天然是线性扫描用迭代的方式最稳。4. 最长有效括号子串三个问题中最难啃的骨头第三个问题才是真正拉开差距的地方给定一个只包含左括号和右括号的字符串找出最长连续有效括号子串的长度。比如(()的最长有效子串是()长度2)()())的最长有效子串是()()长度4()(()的最长有效子串是()长度2——注意最后那对括号和前面的括号之间被一个孤立的(隔断了所以不能连起来。这个题为什么难因为“有效子串”和“有效子序列”完全是两回事。子序列可以跳着选所以只要左右括号数量相等就一定可以组成有效序列但子串必须是连续的中间有一个多余的括号整个连续段就断了。这个“连续性”要求正是动态规划能够大展拳脚的地方。4.1 动态规划解法状态转移是核心动态规划的第一步是定义状态。设dp[i]表示以位置i结尾的最长有效括号子串的长度。注意这里说的是“以 i 结尾”不是“从 0 到 i 的最长有效子串长度”这个定义差别很容易搞混但很重要因为这样才能精确地处理位置i和它前面的字符之间的衔接关系。状态转移需要分几种情况如果s[i] (那以它结尾的有效子串长度为0因为有效子串不可能以左括号结尾。如果s[i] )看前一个字符如果s[i-1] (那s[i-1]和s[i]组成一对dp[i] dp[i-2] 2当然要保证i-2存在。如果s[i-1] )那要看s[i - dp[i-1] - 1]是不是左括号。如果是那它能把dp[i-1]这一整段有效子串包起来再加上开头处左括号前面的那段有效长度即dp[i] dp[i-1] 2 dp[i - dp[i-1] - 2]。我用一个例子拆解这个转移。字符串()(())我们一个个推i0(dp[0]0。i1)前一个是(所以dp[1] dp[-1] 2 2。这里dp[-1]越界当0处理。i2(dp[2]0。i3(dp[3]0。i4)前一个是(所以dp[4] dp[2] 2 2。这时以4结尾的最长有效子串是()。i5)前一个是)dp[4]2所以看i - dp[4] - 1 5 - 2 - 1 2这个位置它是(可以和s[5]配对。于是dp[5] dp[4] 2 dp[1] 2 2 2 6。这里dp[1]的意义是当索引2的左括号和索引5的右括号匹配后左括号前面的那段有效子串长度也需要加进来因为“左括号前紧挨着的那段”和“括号内那段”是连续的。所以整个串从0到5都是有效的长度6。这个转移是这道题最核心的公式理解透彻之后代码写起来就水到渠成。int longestValidParentheses(string s) { int n s.size(), res 0; vectorint dp(n, 0); for (int i 1; i n; i) { if (s[i] )) { if (s[i-1] () { dp[i] (i 2 ? dp[i-2] : 0) 2; } else if (i - dp[i-1] - 1 0 s[i - dp[i-1] - 1] () { dp[i] dp[i-1] 2; if (i - dp[i-1] - 2 0) { dp[i] dp[i - dp[i-1] - 2]; } } res max(res, dp[i]); } } return res; }4.2 栈解法索引进栈一石二鸟动态规划虽然优雅但状态转移公式容易记混。另一种更直观的解法是利用栈来记录左括号的索引同时在栈底保存一个“最后一个未匹配的右括号”的位置作为分界线。核心思路是遍历字符串遇到(就把它的索引入栈遇到)就弹出栈顶如果弹出后栈为空说明i到“栈底标记位置”之间全是有效子串如果弹出后栈不为空说明i到栈顶索引之间是有效子串。这个“栈底标记位置”要先用一个初始值通常是-1表示虚拟的分界点每次遇到无法匹配的右括号时更新这个分界点。int longestValidParentheses(string s) { stackint st; st.push(-1); int res 0; for (int i 0; i s.size(); i) { if (s[i] () { st.push(i); } else { st.pop(); if (st.empty()) { st.push(i); } else { res max(res, i - st.top()); } } } return res; }这个写法我特别喜欢因为它把“分隔点”和“栈”结合得非常巧妙。举个例子对于字符串))(())初始化栈[-1]。i0右括号弹出-1栈空压入0。此时栈[0]。i1右括号弹出0栈空压入1。此时栈[1]。i2左括号压入2。此时栈[1, 2]。i3左括号压入3。此时栈[1, 2, 3]。i4右括号弹出3栈非空栈顶是2更新res max(0, 4-2) 2。i5右括号弹出2栈非空栈顶是1更新res max(2, 5-1) 4。栈底那个元素在整个过程中扮演的角色极其关键它保存的是“最后一个无法匹配的右括号索引”所有有效子串都不可能跨过这个索引。一旦右侧新的一对括号匹配成功它就能和你前一段之间形成更长的一段连续区间吗并不能因为它们之间隔着那个分界点。这个分界点会一直待在栈底直到新的无法匹配的右括号出现时被替换。4.3 正反两次扫描不用栈也不用DP的黑马解法还有一种解法在竞赛里很常见正向扫描一遍反向扫描一遍各用两个计数器left和right。正向扫描时遇到(则left遇到)则right当left right时更新答案当right left时说明这一段已经失效要把两个计数器都清零。反向扫描则反过来遇到)则right遇到(则left当left right时清零。int longestValidParentheses(string s) { int left 0, right 0, res 0; for (int i 0; i s.size(); i) { if (s[i] () left; else right; if (left right) res max(res, left right); else if (right left) left right 0; } left right 0; for (int i s.size() - 1; i 0; i--) { if (s[i] )) right; else left; if (left right) res max(res, left right); else if (left right) left right 0; } return res; }为什么需要正反两遍扫因为单遍扫描对(()这种字符串无能为力正向扫描到结尾时left2, right1永远不会相等但答案是2是存在的。反向扫描就能捕捉到这种情况因为从右往左看right1, left1时相等了答案更新为2。这个解法的空间复杂度是O(1)非常省但如果第一次见到这个思路确实会困惑为什么要扫两遍。我的体会是如果你在面试中能把“为什么要做反向扫描”讲清楚远比背出代码更有说服力。4.4 复杂度与场景对比三种解法的对比可以整理成这样一张表解法时间复杂度空间复杂度核心优势核心劣势动态规划O(n)O(n)状态转移本质清晰一次遍历转移公式繁琐索引偏移容易错栈索引O(n)O(n)直观容易理解和有效性判断衔接自然需要维护分界点概念正反两次扫描O(n)O(1)空间最省思路有创意需要解释两遍扫描的原因实际面试中我推荐的回答路径是先说栈索引的暴力优化思路再顺势提动态规划公式。如果面试官追问“能不能不用额外空间”再把正反两次扫描的方案拿出来。这能体现你从通用方案到特化方案的思考过程。5. 面试官视角与工程实战括号问题的真实面貌这一节聊点题外话但可能是对读者最有用的部分括号问题在面试里到底怎么问以及现实工程项目里它到底有什么用。5.1 面试中的典型追问链面试官通常不会只让你写一个孤立的括号判断。比较常见的追问节奏是“写一个函数判断括号字符串是否有效。”——基础题考察栈。“如果括号有三类怎么写”——考察你是不是只会背题。“现在给你一个很长的字符串找出最长的有效括号子串。”——考察从基础到进阶的思维跳跃。“如果要你顺便输出最大深度怎么办”——考察你在写一版代码时能不能同时满足多个需求。我见过不少候选人在第一问答得很顺到第三问直接卡住。原因在于他们习惯了背诵型刷题没理解三道题背后的共同逻辑。其实如果你在第一问的栈解法里就把“栈顶索引”这个思想想透后面的最长有效子串根本不需要死记硬背现场推演就能推出来。5.2 在编辑器、编译器里的应用场景抛开面试括号匹配的工程应用多得超乎想象代码编辑器的括号高亮IDE里你把光标放在一个左括号上它自动高亮匹配的右括号本质上就是栈匹配的实时版本。编译器的语法分析表达式解析器在读取(a b) * c时需要明确知道每个括号包裹的范围才能构建正确的语法树。lint工具的括号完整性检查很多静态检查工具会报告“未闭合的括号”“多余的右括号”这类规则底层就是括号有效性判断。配置文件解析许多配置格式用括号表示嵌套结构解析器需要实时追踪深度来校验格式正确性。特别有意思的是深度检查。配置文件里偶尔能看到几十层嵌套的括号这并不会报错但如果你的解析器用递归下降法实现过深的嵌套会导致调用栈溢出崩溃现象非常恐怖。解决方案就是提前扫描一遍计算最大深度超限就直接拒绝解析这比崩溃后靠日志查问题要靠谱得多。5.3 实战中容易踩的坑清单自己在真实项目里写过括号解析的人一定会碰到下面这些问题大括号、中括号、括号混合时只判断数量不判断类型。这是最常见也是最隐蔽的bug因为数量相等并不等于配对正确。字符串字面量里的括号被误判。处理源代码时(出现在字符串里时不该参与括号匹配这需要词法分析器先过滤字符串和注释。编码问题导致的不可见字符混入输入。比如全角括号(和半角括号(混在一起肉眼几乎分辨不出来但程序不会把它们当作同一种字符。窗口过大或嵌套过深时的性能退化。如果每次都从头扫描字符串复杂度会变成O(n^2)正确做法是一次扫描边处理边记录。在工程里我倾向于把括号检查写成独立的工具函数输入是一个字符串输出是“是否有效”“最大深度”“最长有效子串长度”这三个值配合单元测试覆盖各种边界这样才能防止后续重构时不小心改坏逻辑。5.4 一段可运行的完整示例把三个问题合在一起写一个完整的函数输出一个字符串的“有效性、最大深度、最长有效子串长度”三个指标应该是这样#include iostream #include stack #include vector #include algorithm using namespace std; struct Result { bool valid; int maxDepth; int longestValid; }; Result analyzeParentheses(const string s) { int depth 0, maxDepth 0; bool valid true; for (char c : s) { if (c () { depth; maxDepth max(maxDepth, depth); } else if (c )) { if (depth 0) { valid false; break; } depth--; } } if (depth ! 0) valid false; int longest 0; stackint st; st.push(-1); for (int i 0; i s.size(); i) { if (s[i] () { st.push(i); } else { st.pop(); if (st.empty()) { st.push(i); } else { longest max(longest, i - st.top()); } } } return {valid, maxDepth, longest}; } int main() { string s )()(()); Result r analyzeParentheses(s); cout valid: r.valid endl; cout maxDepth: r.maxDepth endl; cout longestValid: r.longestValid endl; return 0; }这段代码融合了栈匹配和栈索引两种方法一次输入得到全部三个指标。实际输出为valid: 0因为字符串以右括号开头整个串不合法maxDepth: 2因为(())部分的深度是2longestValid: 4因为()(())中间那段(())加上前面的()实际是连续的长度为4。这个小程序拿来当工具用或者作为刷题模板都很顺手。6. 常见问题与排查技巧实录写这题的过程中每个解法都有对应的坑。我把自己实际调试时遇到的高频问题整理成了一份速查表直接照着排查就行。现象可能的原因排查方法与对策有效字符串被判成无效计数器法用在了多类型括号上确认输入是否只有一种括号多类型一律用栈最大深度始终为0没有更新历史峰值只更新了当前深度每次入栈后要执行maxDepth max(maxDepth, depth)最长有效子串长度少2漏掉了匹配括号前那段有效长度检查dp转移中是否包含dp[i - dp[i-1] - 2]栈索引解法结果不对栈底初始值没设为-1或者分界点更新错了确认每次栈空后都把当前右括号索引压入输入字符串很长时超时用了O(n^2)或O(n^3)的暴力算法改用动态规划、栈或双扫描法压缩到O(n)空字符串返回异常没有对空串做特判空串的有效性是true深度0最长长度0字符串包含其他字符时结果错乱没有过滤非括号字符统一先跳过非括号字符再进入匹配流程递归解法栈溢出嵌套深度过大递归层数太多改用迭代式栈或计数器法除了这些我再分享几个实际操作里的小经验。第一个是调试动态规划时别只看结果把dp数组打出来观察每个位置的值是否符合预期。第二个是写栈解法时考虑用索引而不是字符入栈这样既能做匹配又能算长度是更高级的写法。第三个是如果要在生产代码里用记得加注释和单元测试尤其是那些反直觉的用例比如)(、(()、))(())这些往往就是出bug的地方。最后再说一个实用场景如果你在写一个自动格式化工具需要处理用户输入的半结构化文本括号检查函数可以直接作为前置校验器。用户提交之前先告诉他“第8行少了一个右括号”比事后解析报错要友好太多。这种体验改进底层靠的就是这么一个小函数所以千万别小看括号问题。7. 从刷题到工程这个知识点还能怎么延伸括号问题刷透了还有很多变体和延伸方向值得关注这里简单提几个进阶方向给学有余力的读者一些指引。第一个是带通配符的括号匹配。比如字符串里可能出现*它可以被当作左括号、右括号或空字符判断是否存在一种替换方式让字符串变得有效。这个变体在面试中也经常出现思路是用两个计数器分别模拟左括号的最大值和最小值范围复杂度依然是O(n)但理解难度比基础版高不少。第二个是括号配对后输出配对索引。比如给定((()))输出每一对括号的起止索引。这个只靠计数器做不到必须用栈记录左括号的索引遇到右括号时弹出栈顶左括号索引并配对。这个功能在IDE高亮和代码折叠里非常有用。第三个是最小添加次数使括号有效。给定一个括号字符串问至少添加多少个括号可以让它变得有效。这个问题的解法比“判断有效性”更进一步本质也是在扫描过程中记录右括号多余次数和左括号残余次数最后加起来就是答案。第四个是把问题推广到多种括号且要求输出具体的错误位置。当你需要写一个真正可靠的linter时会发现不仅要判断对错还要告诉用户错在哪一行哪一列这时候需要记录每个字符的位置信息代码会比刷题版本复杂得多但核心依然是栈。这些延伸方向每一条都可以单独写一篇文章但它们的基础都是这篇文章里的三个核心问题。把基础吃透了遇到变体时你只需要在原有逻辑上做增量修改而不是重新学一套东西。我自己在带新人时有一个习惯让他们先做十遍不带任何外部参考的基础括号题直到闭眼能写正确再开始尝试变体。这个策略看起来慢实际上是最快建立直觉的路径。因为括号匹配的直觉一旦建立起来不只是栈用得熟练连带着“最近匹配”“回退”“连续段划分”这些概念都会融会贯通对后续刷动态规划和区间类题目都有不小帮助。如果看完这篇文章你能独立写出同时输出三个指标的完整函数并且能讲清楚动态规划每一步的转移含义那这题就算真正吃透了。剩下的无非是多见变体、多写边界用例、多体会工程场景里的应用方式。括号虽小里面的门道一点都不少。
