---

1541. 平衡括号字符串的最少插入次数

• 标签：栈、贪心、字符串
• 难度：中等

题目链接

• 1541. 平衡括号字符串的最少插入次数 - 力扣

题目大意

描述：给定一个只包含 '(' 和 ')' 的字符串 $s$。可以在任意位置插入 '(' 或 `')'$。

要求：返回使字符串平衡所需的最少插入次数。平衡条件：每个左括号必须对应两个连续的右括号 "))"。

说明：

• $1 \le s.length \le 10^5$。

示例：

• 示例 1：

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

• 示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。

解题思路

思路 1：贪心模拟

1. 核心思想

遍历字符串，维护需要的右括号数 $need$ 和插入次数 $ans$。

遇到 '(' 时，需要两个 ')'，$need += 2$。如果当前有奇数个待匹配的右括号，说明之前可能需要插入一个 ')'。

遇到 ')' 时：

• 如果当前没有待匹配的右括号（$need == 0$），需要插入一个 '('，然后 $need = 1$。
• 否则 $need -= 1$。

2. 具体步骤

第 1 步：初始化 $need = 0$（需要的右括号数），$ans = 0$（插入次数）。

第 2 步：遍历每个字符：

• 如果 $ch == '('$：
  • $need += 2$。
  • 如果 $need \% 2 == 1$（奇数），说明需要先插入一个 ')' 补成偶数（因为每个 '(' 需要一对右括号）。$ans += 1$，$need -= 1$。
• 如果 $ch == ')'$：
  • 如果 $need == 0$：$ans += 1$（插入一个 '('），$need = 1$。
  • 否则 $need -= 1$。

第 3 步：最后 $ans += need$（补全剩余的右括号）。

3. 举例说明

以 $s = "(()))"$ 为例：

• '('：$need=2$。
• '('：$need=4$。
• ')'：$need=3$。
• ')'：$need=2$。
• ')'：$need=1$。
• 结束：$ans += need = 1$。

总插入 $1$ 次，补一个 ')' → (())))"。

以 $s = "())"$ 为例：

• '('：$need=2$。
• ')'：$need=1$。
• ')'：$need=0$。
• 结束：$need=0$，$ans=0$。已平衡。

以 $s = "))")("$ 为例：

• ')'：$need=0$，插入 '('，$ans=1$，$need=1$。
• ')'：$need=0$（消耗一个右括号）。
• ')'：$need=0$，插入 '('，$ans=2$，$need=1$。
• '('：$need=3$（$2+1$），奇数。
• 结束：$ans += need = 5$。

思路 1：代码

class Solution:
    def minInsertions(self, s: str) -> int:
        need = 0  # 需要的右括号数
        ans = 0   # 插入次数

        for ch in s:
            if ch == '(':
                need += 2
                if need % 2 == 1:  # 奇数个右括号，先补一个
                    ans += 1
                    need -= 1
            else:
                if need == 0:
                    ans += 1      # 补一个 '('
                    need = 1
                else:
                    need -= 1

        ans += need
        return ans

思路 1：复杂度分析

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