921. 使括号有效的最少添加

题目链接（中等）

题目描述

只有满足下面几点之一，括号字符串才是有效的：

• 它是一个空字符串，或者
• 它可以被写成 AB（A 与 B 连接），其中 A 和 B 都是有效字符串，或者
• 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s，在每一次操作中，你都可以在字符串的任何位置插入一个括号。返回为使结果字符串 s 有效而必须添加的最少括号数。

数据范围：

• 1 <= s.length <= 1000
• s 只包含 '(' 和 ')' 字符

示例

示例 1：

输入： s = "())"
输出： 1
解释： 在开头插入一个 '('，得到 "(())"，有效。

示例 2：

输入： s = "((("
输出： 3
解释： 在末尾添加 3 个 ')'，得到 "((()))"，有效。

核心思路

贪心：从左到右扫描，维护「当前未匹配的左括号数」need：

• 遇到 '('：need += 1；
• 遇到 ')'：
  • 若 need > 0：说明有左括号可以匹配，need -= 1；
  • 若 need == 0：说明这个右括号没有左括号匹配，必须补一个左括号，ans += 1。

扫描结束后，need 个左括号还没有右括号匹配，每个都要补一个右括号，所以 ans += need。

为什么贪心最优：

• 每个多余的右括号（前面没有左括号可匹配）必须补一个左括号，没有其他办法；
• 每个未匹配的左括号必须补一个右括号，也没有其他办法；
• 每个右括号都尽量匹配最近的左括号，不会让后面的匹配变差（因为左括号数量只减不增，早匹配和晚匹配对后续影响相同）。

因此「遇到右括号能匹配就匹配，不能匹配就补左括号」的贪心策略最优。

方法：贪心

思路及解法

用两个变量：

• need：当前未匹配的左括号数量；
• ans：已经需要添加的括号数量。

遍历字符串：

1. '('：need += 1；
2. ')'：
   • need > 0：need -= 1（匹配掉一个左括号）；
   • need == 0：ans += 1（需要补一个左括号）。

遍历结束后，ans + need 就是答案（need 个左括号各补一个右括号）。

代码

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        need = 0      # 当前未匹配的左括号数
        ans = 0       # 需要添加的括号数

        for ch in s:
            if ch == '(':
                need += 1
            else:
                if need > 0:
                    need -= 1
                else:
                    ans += 1      # 多余的右括号，必须补一个左括号

        # 剩余的左括号各补一个右括号
        return ans + need

复杂度分析

• 时间复杂度：$O(n)$，遍历一次字符串。
• 空间复杂度：$O(1)$，只使用两个变量。

另一种写法：balance 取最小值

思路及解法

用 balance 表示「左括号数 - 右括号数」，维护 balance 的历史最小值 min_balance：

• 最终答案 = balance_end - min_balance。

直觉：

• balance 变成负数时，说明右括号多了，需要补左括号；
• min_balance 记录了「最缺左括号」的程度，这部分必须补左括号；
• balance_end 是最终剩余的左括号数，这部分必须补右括号。

代码

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        balance = 0
        min_balance = 0

        for ch in s:
            if ch == '(':
                balance += 1
            else:
                balance -= 1
                min_balance = min(min_balance, balance)

        return balance - min_balance

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

两种写法对比

写法	时间	空间	特点
need + ans	$O(n)$	$O(1)$	最直观，逐步累加
balance + min_balance	$O(n)$	$O(1)$	数学化，代码更短

推荐：面试时用第一种 need + ans 写法，逻辑最清晰，容易讲。

关键细节

1. 为什么多余的右括号一定要补左括号

如果当前 need == 0 却遇到 ')'，说明这个右括号前面没有任何未匹配的左括号。唯一的办法就是在它前面插入一个左括号，否则它永远无法匹配。

2. 为什么剩余左括号一定要补右括号

扫描结束后，need 个左括号没有被匹配，唯一的办法是在它们后面各插入一个右括号。

3. 为什么贪心不会错过最优解

对于每个右括号：

• 如果有左括号可以匹配，匹配它是「免费」的，不会增加成本；
• 如果不匹配，就必须补一个左括号，成本 +1。

匹配一个可用的左括号，不会让后续的匹配变差（左括号数量只减不增，早晚都要用），所以贪心匹配一定是最优的。

4. 与 LC 20（有效的括号）的区别

• LC 20：判断是否有效，返回布尔值；
• LC 921：允许插入括号，求最少插入数。

LC 20 的栈方法也可以用来解 LC 921（栈的大小就是需要补的括号数），但 need 计数更省空间。

5. 与 LC 32（最长有效括号）的区别

• LC 32：求最长有效子串长度；
• LC 921：求使整个串有效的最少插入数。

前者是「找最长的一段」，后者是「补齐整个串」。

6. 与 LC 1249（移除无效的括号）的区别

• LC 921：只能插入括号；
• LC 1249：只能删除括号。

两者都是「使括号串有效」的问题，但操作方向相反，贪心逻辑也不同。

总结

• 贪心核心：能匹配就匹配，不能匹配就补；
• need + ans 写法：
  • (：need += 1；
  • )：need > 0 则 need -= 1，否则 ans += 1；
  • 最终答案 ans + need；
• balance + min_balance 写法：答案 = balance_end - min_balance；
• 时间复杂度 $O(n)$，空间复杂度 $O(1)$；
• 通用套路：「最少插入使括号有效」→ 贪心，维护未匹配左括号数。

相关题目

• LC 20. 有效的括号（判断整体是否有效）
• LC 22. 括号生成（生成所有有效括号）
• LC 32. 最长有效括号（求最长有效子串）
• LC 301. 删除无效的括号（删除最少括号）
• LC 1249. 移除无效的括号（删除无效括号，求结果）
• LC 1541. 平衡括号字符串的最少插入次数（进阶版，每个左括号需要两个右括号）