LeetCode 921中等贪心
使括号有效的最少添加 图解题解
这道题到底在问什么
只含 ( 和 ) 的字符串 s。每次可在任意位置插入一个括号。求让 s 变成有效括号串所需的最少插入次数。
- s
- "()))(("
- 输出
- 4
- 解释
- 补 2 个 ( 配前面多的 ))，再补 2 个 ) 配后面多的 ((
最优解：一步一步想明白
- 3遇 ( 就 open+1(攒着等右括号);遇 ) 先看手里有没有 ( 能配——有就 open−1(配掉),没有就 need+1(这个 ) 注定要补一个 ( )。
- 4下面拿 "()))((" 一格一格演。盯住屏幕下方的 open 和 need 两个数怎么随指针变化。
- 5open=0 need=0字符串 "()))((" 摊成 6 格。指针停在第 0 位,两个计数器都从 0 起步。
- 6遇 ( → open: 0→1第 0 位是 (,把它攒进手里:open 从 0 变 1。它在等右边出现一个 ) 来配对。
- 7open=1 need=0第 0 位处理完(变灰),指针挪到第 1 位。手里还攒着 1 个没配对的 (。
- 8open>0 → open: 1→0第 1 位是 ),而手里正好有 1 个 (。配对成功:open 减回 0。这两格(绿)就是已经合法的一对。
- 9open=0 need=0前两格配成一对,封存变灰。指针到第 2 位。注意现在 open=0——手里没有空闲的 ( 了。
- 10open=0 → need: 0→1第 2 位又是 ),可手里 open=0,没有 ( 能配它!这个孤儿 ) 只能记账:need 从 0 变 1,将来必须给它补一个 (。
- 11open=0 need=1第 2 位那个孤儿 ) 记完账(标红),指针到第 3 位。现在 need=1:已经欠了 1 个左括号。
- 12open=0 → need: 1→2第 3 位还是 ),open 依旧是 0,又一个孤儿!need 从 1 变 2。现在欠了 2 个左括号。
- 13open=0 need=2两个孤儿 ) 都记账了(标红),need 累到 2。指针到第 4 位,接下来是两个 (。
- 14遇 ( → open: 0→1第 4 位是 (,攒进手里:open 从 0 变 1。它在等右边的 ) 来配,可惜后面没有了——先记着。
- 15open=1 need=2指针到最后第 5 位。手里攒着 1 个没配对的 (,欠债 need 仍是 2。
- 16遇 ( → open: 1→2第 5 位还是 (,再攒一个:open 从 1 变 2。这两个 ((都没有右括号能配,扫完后它们就是「余量」。
- 17open=2 need=26 格全扫完。结算:手里余下 open=2 个左括号(绿,各缺一个 ))、need=2 个孤儿右括号(红,各缺一个 ()。
- 182 + 2 = 4 ✓把两笔账加起来:欠的 2 个 ( 要补、余的 2 个 ) 也要补,一共补 4 个,字符串才合法。答案就是 4。
- 19open=0 need=0换 "(()" 再走一遍,这次专看雷区②说的结尾余下 open。指针停在第 0 位,计数器归零。
- 20open: 0→1第 0 位 (,攒进手里:open = 1。
- 21open: 1→2第 1 位又是 (,再攒一个:open = 2。手里现在攒着两个左括号。
- 22open>0 → open: 2→1第 2 位 ),手里有 ( 可配,配掉一对:open 从 2 减到 1。全程没出现孤儿,need 一直是 0。
- 23open=1 need=0 → 1结算:余下 1 个没配对的 (((第 0 位,标灰),它缺一个 ),所以补 1 个就合法,答案 1。验证了「结尾余下的 open 也要补」。
- 24孤儿 ) 总出现在余下 ( 的左边(位置 2、3 在 4、5 之前),所以一个补在左、一个补在右,谁也救不了谁,只能各补各的——这正是 need+open 不能再少的原因。
- 28"(((" 若只返回 need拿 "(((" 试:全是 (,没有任何孤儿 ),need 一直是 0。要是只返回 need 就得 0——大错!其实 3 个 ( 各缺一个 ),必须补 3 个。这就是为什么结尾要加 open。
⚠️ 容易写错的地方
✗ 错：遇 ) 时直接 need++
✓ 对：先看 open>0 能不能配,能配就 open−−
不先尝试配对会把本来合法的对子也算成缺口,答案偏大
✗ 错：扫完只返回 need,忘了 open
✓ 对：返回 need + open
结尾余下的 ( 也都缺右括号,漏加 open 会少算
完整代码（Python / C++ / Java）
Python
class Solution:
def minAddToMakeValid(self, s):
open_ = 0 # 没配对的 ( 数
need = 0 # 必须补 ( 的孤儿 ) 数
for c in s:
if c == '(':
open_ += 1
elif open_ > 0: # ) 且手里有 ( 可配
open_ -= 1
else: # ) 但没 ( 可配
need += 1
return need + open_C++
class Solution {
public:
int minAddToMakeValid(string s) {
int open = 0, need = 0;
for (char c : s) {
if (c == '(') {
open++;
} else if (open > 0) { // ) 且有 ( 可配
open--;
} else { // ) 无 ( 可配
need++;
}
}
return need + open;
}
};Java
class Solution {
public int minAddToMakeValid(String s) {
int open = 0, need = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
open++;
} else if (open > 0) { // ) 且有 ( 可配
open--;
} else { // ) 无 ( 可配
need++;
}
}
return need + open;
}
}复杂度
时间复杂度
O(n)
从左到右扫一遍字符串,每个字符只看一次,n 为字符串长度
空间复杂度
O(1)
只用了 open、need 两个整数计数器,不随输入规模增长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使括号有效的最少添加 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 need 和 open 不能互相抵消?+
孤儿 ) 一定在余下 ( 的左边(否则那个 ( 会先把它配掉),一个要补在左、一个要补在右,无法合并,所以是相加。
能用栈做吗?+
能。遇 ( 入栈,遇 ) 时栈非空就弹栈否则 need++,最后 need+栈内剩余 ( 数 = 答案。计数法就是把栈替换成一个计数器 open。
进阶 LC1541 带权重(每个 ( 要两个 ))怎么变?+
思路相同但要维护需要的 ) 数,遇 ( 时若当前缺奇数个 ) 要先补齐,逻辑更细但仍是一遍扫描计数。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使括号有效的最少添加 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。