最近在准备算法面试的话LeetCode 1249 移除无效的括号 这道题应该不陌生。它几乎是面试里最典型的“看着简单、一写就错”的题目考点很清晰就是括号匹配和字符串处理但很多人第一版代码直接把自己绕进去。题目要求从一个包含小写字母和括号的字符串里删掉尽量少的括号让剩下的括号全部配对返回任意一个合法结果。说人话就是把字符串里所有“单着”的括号清理干净。这篇文章会把这道题从暴力思路到最优解全部拆开讲覆盖栈解法、两遍扫描计数法、边界条件、面试追问和常见坑。不管你是刚开始刷题的新手还是准备冲刺大厂面试都能拿到可以直接用的模板和避坑清单。1. 题面拆解先搞懂“最少删除”到底要删什么1.1 从“有效括号”的定义说起所谓有效字符串规则只有两条每个右括号都必须有一个在它之前出现的左括号和它配对每个左括号都必须有一个在它之后出现的右括号和它配对。换句话说从左往右扫的时候左括号的累计数量永远不会小于右括号的累计数量且最终两者数量相等。这个规则在题目里有一个很友好的前提字符串里除了括号和字母没有别的符号。所以不用考虑引号、转义、注释这些干扰项问题被压缩到了最纯粹的括号配对。那“移除最少数量的无效括号”是什么意思举个例子a)b(c)d里只有下标 2 的那个右括号是孤立的删除它之后变成ab(c)d括号全部合法。再比如lee(t(c)o)de)末尾多了一个右括号删掉它就行。但(((这种就麻烦了三个左括号全部孤立只能全删结果是空串。有一个容易被忽略的点题目只要求返回“任意一个”有效结果不是所有结果。这就把难度从搜索问题降级成了构造问题。如果要求返回所有可能结果那就是另一道题了后面我会专门讲。1.2 核心考点与常见误区这道题真正想考的东西有三个栈的典型应用、贪心/计数的思想、字符串不可变性的工程处理。先说栈。括号匹配问题最经典的手段就是栈——看到左括号入栈看到右括号弹栈。但很多新手会踩同一个坑栈里存的是字符本身而不是下标。如果存字符遍历完之后你只知道“有多少个括号没匹配上”却不知道它们在原字符串的哪个位置输出结果时完全无从下手。正确做法是入栈时把下标存进去。再说贪心/计数。其实不用栈也能做两遍扫描计数法同样是 O(n) 时间而且空间上更省。它依赖的思路是从左到右先清掉所有“没有左括号可配对”的右括号再从右到左清掉所有“没有右括号可配对”的左括号。这两轮互不干扰各自贪心合起来就是全局最少删除。常见的误区有三个。第一个是只处理多余的右括号忘了最后处理多余的左括号第二个是在循环里频繁用result c拼字符串Python 里字符串不可变循环拼接会变成 O(n²)长字符串直接超时第三个是把这道题当成 301 删除无效括号那种“返回所有结果”的题目非要用回溯反而把简单问题做复杂了。先记住一个结论只要求一个结果时优先想贪心构造不要一上来就搜索。2. 栈解法一次扫描定位所有孤儿括号附完整代码2.1 为什么栈里必须存下标栈里存下标核心是为了最后“精准打击”。遍历过程中每个合法匹配都会通过弹栈抵消掉遍历结束后栈里剩下的是所有没能匹配上的左括号下标。而遍历过程中遇到的、在栈为空时出现的右括号则是没能匹配上的右括号下标。两类下标放在一个删除标记集合里最后扫一遍原字符串只输出没被标记的字符就得到答案了。整个过程我建议按照这个顺序手推一遍字符串a)b(c)d下标从 0 开始a不处理下标 1 是)栈为空标记删除下标 3 是(入栈下标 5 是)栈不为空弹栈这一对匹配成功遍历结束栈为空。最终被标记的只有下标 1结果就是ab(c)d。为什么不直接用一个计数器balance代替栈因为计数器只能告诉我“有没有多余的左括号”不能告诉我“多余的左括号在哪个位置”。栈的本质是“记住位置的历史”配合集合标记才能做到一次扫描出结果。2.2 完整代码实现与逐行注释Python 版本应该是全网最常见的一种写法def minRemoveToMakeValid(s: str) - str: stack [] to_remove set() for i, ch in enumerate(s): if ch (: stack.append(i) elif ch ): if stack: stack.pop() else: to_remove.add(i) while stack: to_remove.add(stack.pop()) return .join(ch for i, ch in enumerate(s) if i not in to_remove)解释几个关键细节遇到左括号无条件入栈因为此时无法判断它将来能不能匹配上必须等后面的右括号来“认领”。遇到右括号先看栈里有没有存货。有就弹出一个左括号和它配对没有就说明这个右括号是孤儿的标记删除。循环结束后栈里剩的全是孤儿左括号一次性全部加入删除标记。最后用enumerate同时拿下标和字符过滤掉标记位置拼接结果。Java 的写法则要注意字符串构建用StringBuilder别用字符串public String minRemoveToMakeValid(String s) { DequeInteger stack new ArrayDeque(); SetInteger toRemove new HashSet(); for (int i 0; i s.length(); i) { char c s.charAt(i); if (c () { stack.push(i); } else if (c )) { if (!stack.isEmpty()) { stack.pop(); } else { toRemove.add(i); } } } while (!stack.isEmpty()) { toRemove.add(stack.pop()); } StringBuilder sb new StringBuilder(); for (int i 0; i s.length(); i) { if (!toRemove.contains(i)) { sb.append(s.charAt(i)); } } return sb.toString(); }C 的写法和 Java 类似用vectorint模拟栈unordered_setint存删除位置class Solution { public: string minRemoveToMakeValid(string s) { vectorint st; unordered_setint del; for (int i 0; i s.size(); i) { if (s[i] () st.push_back(i); else if (s[i] )) { if (!st.empty()) st.pop_back(); else del.insert(i); } } for (int i : st) del.insert(i); string res; for (int i 0; i s.size(); i) { if (del.find(i) del.end()) res.push_back(s[i]); } return res; } };提示如果追求极致性能可以把Set换成一个boolean[]标记数组。下标就是数组索引查询是 O(1) 的数组访问比哈希结构更快。缺点是如果字符串很长且括号很少会浪费一些空间建数组。实际刷题时两者都能过但面试时能主动说出这个优化会显得你有工程意识。2.3 时间与空间复杂度分析时间复杂度是 O(n)一次遍历标记一次过滤拼接每个字符被常数次操作。空间复杂度是 O(n)栈最多存 n 个下标删除标记集合最多存 n 个下标结果字符串长度不超过 n。有没有可能把空间压到 O(1)如果只要求返回新字符串输出空间本身不可避免但如果允许原地修改字符数组可以用“标记占位符”的方式配合两遍扫描额外空间只需要两个整数变量。这个思路放在下一节专门讲理解了它对这道题的理解会上一个台阶。3. 两遍扫描计数法空间更省的进阶思路附 Java 实现3.1 核心思想分方向清掉“单边多余”的括号栈解法很直观但很多人写完会想真的需要栈吗其实不需要。两遍扫描计数法的思想更接近人类手工处理括号的方式。第一遍从左往右扫描维护一个balance计数器表示当前已经扫描到的未匹配左括号数量。遇到(就加一遇到)时如果balance 0就减一说明这个右括号能和前面的某个左括号匹配如果balance 0说明这个右括号前面没有多余的左括号可供配对它自己就是多余的直接删除。这一遍结束后所有“多出来的右括号”都被清掉了。但问题还没完字符串里可能还残留着多出来的左括号。比如(((第一遍没有右括号需要处理三个左括号全被留下来了。这时候需要第二遍从右往左扫描维护另一个balance表示已经扫描到的未匹配右括号数量。遇到)就加一遇到(时如果balance 0就减一并保留这个左括号如果balance 0说明这个左括号右边没有多余的右括号能和它配对删除。为什么第二遍必须反着扫因为“多余的左括号”本质上是指那些一直找不到右括号匹配的左括号只有当你已经站在字符串末尾往回看时才能确定哪些左括号是“最终被剩下”的。从右往左看左括号和右括号的角色正好互换逻辑完全对称理解起来不费劲。3.2 Python 完整实现def minRemoveToMakeValid(s: str) - str: # 第一遍清除多余的右括号 first [] balance 0 for ch in s: if ch (: balance 1 first.append(ch) elif ch ): if balance 0: balance - 1 first.append(ch) # balance 0 时这个右括号是多余的不加入 else: first.append(ch) # 第二遍从右往左清除多余的左括号 result [] balance 0 for ch in reversed(first): if ch ): balance 1 result.append(ch) elif ch (: if balance 0: balance - 1 result.append(ch) # balance 0 时这个左括号是多余的不加入 else: result.append(ch) return .join(reversed(result))注意第二遍收集结果的顺序是反的最后必须reversed一次。忘记反转是这道题最经典的错误之一。3.3 Java 实现与细节说明public String minRemoveToMakeValid(String s) { StringBuilder first new StringBuilder(); int balance 0; for (char c : s.toCharArray()) { if (c () { balance; first.append(c); } else if (c )) { if (balance 0) { balance--; first.append(c); } } else { first.append(c); } } StringBuilder ans new StringBuilder(); balance 0; for (int i first.length() - 1; i 0; i--) { char c first.charAt(i); if (c )) { balance; ans.append(c); } else if (c () { if (balance 0) { balance--; ans.append(c); } } else { ans.append(c); } } return ans.reverse().toString(); }这里最容易搞混的是第二遍balance的作用。可以把它理解为“右侧还有多少个右括号等着被左括号认领”。从右往左扫的时候遇到右括号就说明右侧多了一个可用的匹配资源遇到左括号时如果能消费一个资源就说明这一对括号在整体上是配对的保留否则删掉。3.4 三种思路横向对比方法时间复杂度额外空间核心优势适合场景栈 下标标记O(n)O(n)直观符合括号匹配直觉天然支持混合括号面试现场快速写对两遍扫描计数法O(n)O(n)输出串不依赖栈结构代码更短逻辑对称追求简洁代码面试进阶原地标记 两遍扫描O(n)O(1)不计输出空间最省适合超长字符串面试炫技工程优化第三种思路值得多说一句把字符串转成字符数组第一遍从左到右把多余的右括号位置改成#之类的占位符第二遍从右到左把多余的左括号位置改成#最后输出时跳过所有占位符。额外空间只有两个计数器。不过它修改了输入数组如果题目允许原地操作这是空间上最优的版本。4. 边界条件、常见坑与面试追问实战4.1 这些边界条件第一次写很容易凉先把测试用例想明白比直接写代码更值钱输入期望输出原因空字符串本身合法aa没有括号原样返回(唯一的左括号无法配对)唯一的右括号无法配对()()已经合法(()()删除一个左括号即可)((右括号孤儿且两个左括号孤儿全部删除a)b(c)dab(c)d典型场景删除孤立右括号lee(t(c)o)de)lee(t(c)o)de典型场景删除末尾多余右括号())(()一个右括号多余另一个左括号多余能把这些用例全部跑通说明对“什么该删、什么该留”已经有了正确的直觉。4.2 常见问题与排查技巧实录写这道题时大家遇到最多的问题其实很集中我整理了一个速查表问题现象根本原因解决办法结果里还剩多余的左括号第一次扫描只处理了右括号没有处理栈里残留的左括号栈解法最后要while stack: to_remove.add(stack.pop())两遍扫描要做第二遍反向扫描结果字符串顺序错乱两遍扫描的第二遍是反向拼接忘记最后反转确保reversed(result)或ans.reverse().toString()长字符串超时循环内用result c拼接字符串Python 字符串不可变导致 O(n²)用list收集字符最后.join(list)不知道删哪个位置的括号栈里存的是字符不是下标改为stack.append(i)存下标输入含有嵌套括号时误删遇到右括号直接弹栈但没考虑匹配位置单类型括号不受影响混合括号要检查栈顶类型结果不是“最少删除”删除策略太激进把本来能匹配的括号也删了检查是否只在balance 0时删右括号、反向扫描只在balance 0时删左括号4.3 面试追问一从 1249 到 301返回所有结果怎么做1249 只要求返回任意一个结果所以贪心就够。但面试官常常会追加一句“如果我要所有可能的结果呢”这就是 301 删除无效的括号。核心思路是先预处理计算出最少需要删除的左括号数量left_rem和右括号数量right_rem。本质上就是统计字符串中无法配对的括号数量。用 DFS 或 BFS 遍历每个字符遇到括号时有“删除”和“保留”两个分支。剪枝条件已经删除的括号数量超过预计算额度直接剪掉过程中保证右括号数量不超过左括号数量否则结果不可能合法。遍历完所有字符且左右删除数都用完同时括号有效就加入结果集合。最终用Set去重。1249 是 301 的“单个结果版”理解 1249 的贪心逻辑后再去写 301 会清楚很多。至少你能准确地算出最少要删几个左括号、几个右括号这本身就是 301 的第一步。提示如果面试时时间不够可以先口头讲清楚 301 的思路不用完整写完代码。重点展示你“知道两者之间的差异”这比闷头写一个冗长的回溯更有价值。4.4 面试追问二混合括号、流式输入和空间优化如果题目把括号升级成()、[]、{}三种类型栈解法仍然是最稳的选择。遇到右括号时不能无脑弹栈要先看栈顶是不是同类型的左括号常见写法是维护一个MapCharacter, Character做配对查询或者直接判断栈顶字符。两遍扫描计数法这时候就比较尴尬因为需要同时维护三套计数器逻辑复杂度明显上升。如果输入是流式的比如从一个管道里逐个字符读入栈方法天然支持增量处理边读边维护栈。两遍扫描法必须等待全部输入结束才能开始第二遍不适合流式场景这也是为什么很多解析器工具里用的是栈而不是计数。如果只要求输出删除数量不需要构造结果字符串最简单从左往右扫一遍遇到右括号时如果左括号余额为 0 就记录一次需要删除遇到左括号就累加最后再把左括号余额加到结果里。这个版本甚至可以做到 O(1) 空间几行代码就写完。另外有人会问这道题的结果唯一吗不唯一。比如(a(b)可以删下标 0 的左括号得到a(b)也可以删下标 3 的左括号得到(ab)两个结果都合法。题目只要求返回任意一个这也是为什么栈解法里用Set标记删除位置、最后按原顺序拼接就能通过——你删掉一个位置剩下的括号自然就是合法的。4.5 一道完整的模拟从输入到输出走一遍最后带大家手动跑一遍稍微复杂一点的例子。输入ab(c(d)e(f)g)所有括号都是配对的两种解法都会原样返回。再看一个经典坏例a(b(c)d)e)末尾多了一个右括号。第一遍从左到右扫描时前面的括号全部正常匹配直到最后那个右括号出现此时计数余额为 0判定为删除。结果变成a(b(c)d)e完全正确。如果输入是)a(b)c(第一遍删除开头的右括号得到a(b)c(第二遍从右往左扫描遇到最后的左括号时余额为 0删除得到a(b)c。这也是最少删除删两个结果合法。手动推演的价值在于你会在实际编码前就建立起“哪一轮删什么括号”的直觉。刷题时我强烈建议先手写两三个例子再碰键盘这两个解法总共不过十几行代码思路通了写起来非常快。最后再分享一点个人的刷题体会我第一次做这道题时用的是栈存字符而不是下标结果代码写完怎么都想不通“该删哪些位置”。后来把栈改成存下标五分钟就过题了。这个教训后来我反复用数据结构里存什么取决于你下游需要什么信息。要定位到具体字符就必须存位置相关的信息这是一个非常通用的编码思维。这道题另一个让我印象深刻的地方是它同时覆盖了三种面试常考能力栈的使用、贪心构造、以及对字符串不可变性的处理。把这些点吃透顺便把 301 删除无效的括号的解题框架也理一遍面试里再遇到同类题目就能直接迁移了。实际工程项目里处理用户输入的公式、解析模板字符串、清洗配置文件时核心逻辑和这道题几乎没有区别——先找到不匹配的位置再精确地删掉需要删的东西。
