题目描述
思路解析
一句话答案：LeetCode 301 删除无效的括号：两遍贪心扫描可求出一个合法解——维护平衡计数 bal，第一遍从左到右删掉每个让 bal 变负的多余右括号，第二遍反向对称地删多余左括号，删的都是必删项，时间 O(n)。官方原题要求列出全部最少删除方案时，需改用 BFS/DFS 枚举。
删除无效的括号在问什么
字符串里混着左右括号和小写字母，要求删掉最少数量的括号，让剩下的串合法——每个左括号都能配到它右边的一个右括号。字母不参与配对、原样保留。这题按删除数量最少来衡量方案好坏，所以核心是想清楚：到底哪些括号是「非删不可」的，除此之外一个都不多删。
为什么想到用平衡计数器 bal
先问一个串怎样才算合法。从左往右数，用 bal 表示「目前左括号比右括号多出几个」：遇左括号加一，遇右括号减一。合法等价于两件事同时成立——扫描全程 bal 从不变负（每个右括号出现时左边都有闲置的左括号等它），且扫完 bal 归零（左括号也都配上了）。
这个刻画直接暴露了谁是多余的：某个右括号让 bal 要变负，说明它左边的左括号已经全被前面的右括号配光了，无论后面发生什么，它都永远配不上对——这就是一个必删的括号。反过来，扫完后 bal 还大于 0，说明有左括号到最后也没等来配对，它们同样必删，只是位置在串的尾部一侧。
为什么必须正反各扫一遍
从左到右的一遍扫描只能当场揪出多余的右括号，因为右括号非法与否取决于它左边的情况，扫到它时证据已经齐了。可多余的左括号不行：左括号能不能配上，取决于它右边还有没有右括号，正向扫到它时未来还没发生，没法判它死刑。
解决办法是对称地反着来一遍：从右往左扫，把右括号当开方、左括号当闭方，bal 的含义变成「右括号比左括号多几个」，让 bal 变负的左括号就是配不上的，删掉。两遍合起来，多余的右括号和左括号都被清干净，剩下的串前缀性质与总量守恒同时满足，必然合法。
凭什么说这样删得最少
每一次删除都发生在「铁证已到手」的时刻：那个括号在当时的局面下无论如何都配不上对，任何合法方案都必须删掉它或某个等价位置的括号，删除数量因此不可能更少。而删掉它之后 bal 停在 0 继续扫，等于当它从没出现过，不牵连任何本来合法的括号——不多删一个。
实现上有个细节要盯住：判定多余的那个括号直接删掉、bal 保持原样不减，等于当它从未出现，绝不能让 bal 落到负数再继续。若放任 bal 变成负数往下走，后面本来合法的右括号会被连累着误判成多余，越删越多。
复杂度、边界与题目变体
时间 O(n)：正反各一遍线性扫描，每个字符只看常数次；空间 O(n)，用一个字符数组标记删除位并拼出结果。易错点除了 bal 忘归零，还有把字母也计入 bal——字母不影响配对，混进计数会把平衡算错，它们只需原样保留。
变体上，如果题目要求返回所有删除数最少的合法方案，两遍贪心就不够了：得先算出左右括号各需删几个，再用 BFS 或 DFS 枚举删哪些位置并去重校验。本题这套线性扫描的价值在于用 O(n) 拿到一个合法解，是面试里性价比极高的起手式。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心就一个计数器 bal：左括号 +1、右括号 -1，谁让它变负谁就是多余的。第一遍删多余的 )，第二遍反向删多余的 (。
第一遍从左往右扫。bal 表示「目前左括号比右括号多出几个」，开始是 0。
指针 i 走到下标 0，这一格是 '('。是左括号，bal 加一。
左括号入账：bal 加一变成 1（高亮的就是它）。它在等一个右括号来配对。
指针 i 走到下标 1，这一格是 ')'。是右括号，bal 减一，再看它是否合法。
bal 大于 0，说明前面有左括号等着配它：bal 减一变成 0，这个右括号合法、保留。
指针 i 走到下标 2，这一格是 '('。是左括号，bal 加一。
左括号入账：bal 加一变成 1（高亮的就是它）。它在等一个右括号来配对。
指针 i 走到下标 3，这一格是 ')'。是右括号，bal 减一，再看它是否合法。
bal 大于 0，说明前面有左括号等着配它：bal 减一变成 0，这个右括号合法、保留。
指针 i 走到下标 4，这一格是 ')'。是右括号，bal 减一，再看它是否合法。
bal 已经是 0，没有左括号能配它——这个右括号是多余的，标红删掉（已删 1 个）。
指针 i 走到下标 5，这一格是 '('。是左括号，bal 加一。
左括号入账：bal 加一变成 1（高亮的就是它）。它在等一个右括号来配对。
指针 i 走到下标 6，这一格是 'a'。是字母，跟括号无关，直接跳过。
指针 i 走到下标 7，这一格是 ')'。是右括号，bal 减一，再看它是否合法。
bal 大于 0，说明前面有左括号等着配它：bal 减一变成 0，这个右括号合法、保留。
指针 i 走到下标 8，这一格是 '('。是左括号，bal 加一。
左括号入账：bal 加一变成 1（高亮的就是它）。它在等一个右括号来配对。
第一遍结束，所有多余的右括号都标红删了。但结尾那个落单的左括号还没处理，需要第二遍。
第二遍从右往左扫。这回把角色对调：遇 ) 加一、遇 ( 减一，删掉多余的左括号。bal 重新从 0 起步。
指针 i 走到下标 8，这一格是 '('。反向扫时左括号当「收口」，bal 减一，再看是否合法。
bal 已经是 0，后面没有右括号能配它——这个左括号是多余的，标红删掉（已删 2 个）。
指针 i 走到下标 7，这一格是 ')'。反向扫时右括号当「开口」，bal 加一。
反向记账：bal 加一变成 1（高亮的就是它），等一个左括号来配。
指针 i 走到下标 6，这一格是 'a'。是字母，跳过。
指针 i 走到下标 5，这一格是 '('。反向扫时左括号当「收口」，bal 减一，再看是否合法。
bal 大于 0，后面有右括号等着配它：bal 减一变成 0，这个左括号合法、保留。
下标 4 这格第一遍已经删了，第二遍直接跳过它。
指针 i 走到下标 3，这一格是 ')'。反向扫时右括号当「开口」，bal 加一。
反向记账：bal 加一变成 1（高亮的就是它），等一个左括号来配。
指针 i 走到下标 2，这一格是 '('。反向扫时左括号当「收口」，bal 减一，再看是否合法。
bal 大于 0，后面有右括号等着配它：bal 减一变成 0，这个左括号合法、保留。
指针 i 走到下标 1，这一格是 ')'。反向扫时右括号当「开口」，bal 加一。
反向记账：bal 加一变成 1（高亮的就是它），等一个左括号来配。
指针 i 走到下标 0，这一格是 '('。反向扫时左括号当「收口」，bal 减一，再看是否合法。
bal 大于 0，后面有右括号等着配它：bal 减一变成 0，这个左括号合法、保留。
两遍扫完，所有标红的格子去掉，剩下的字符拼起来就是 "()()(a)"——删得最少的合法括号串。
三个高频追问：bal 的含义、为何最少、以及「返回全部方案」该怎么变。
参考代码
def removeInvalid(s): arr = list(s) def scan(idx, op, cl): # idx 顺序, op 开括号, cl 闭括号 bal = 0 for i in idx: if arr[i] == op: bal += 1 elif arr[i] == cl: if bal > 0: bal -= 1 else: arr[i] = '' # 多余,删除 scan(range(len(arr)), '(', ')') # 第一遍 删多余 ) scan(reversed(range(len(arr))), ')', '(') # 第二遍 删多余 ( return ''.join(arr)复杂度
- 时间：O(n)，两遍线性扫描，每个字符各看常数次
- 空间：O(n)，用一个字符数组标记/收集结果，n 为串长
易错点
面试追问把动画讲成自己的话
追问bal 这个计数器到底代表什么？
追问为什么这样删一定是「删得最少」的？
追问如果题目要返回所有删最少的合法方案呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题