目标
给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
- 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
- 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。示例 2：
输入：s = "())"
输出：0
解释：字符串已经平衡了。示例 3：
输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。示例 4：
输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。示例 5：
输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。说明：
- 1 <= s.length <= 10^5
- s 只包含 '(' 和 ')' 。
思路
定义平衡括号字符串是每一个左括号都对应有两个连续右括号的字符串。有一个括号字符串 s，每次操作可以插入一个 ( 或者 )，求使括号字符串变平衡的最小操作次数。
记录未匹配的左括号数量 lc，遇到连续的右括号直接滑倒结束并计数 rc，贪心策略：
- 如果
lc >= rc，如果rc为奇数，需要补一个右括号，操作加一，lc减去已匹配的数量，rc置零。 - 否则，每两个右括号匹配需要补一个左括号，操作加
rc / 2，如果rc是奇数，需要补一对括号，操作加2。
代码
/**
* @date 2026-10-09 9:09
*/
public class MinInsertions1541 {
public int minInsertions(String s) {
char[] chars = s.toCharArray();
int n = s.length();
int lc = 0, rc = 0, res = 0;
int i = 0;
while (i < n) {
if (chars[i] == '(') {
lc += 2;
i++;
} else {
while (i < n && chars[i] == ')') {
i++;
rc++;
}
}
if (lc >= rc) {
res += rc % 2;
lc -= rc + rc % 2;
rc = 0;
} else {
rc -= lc;
int rem = rc % 2;
res += rc / 2 + (rem == 0 ? 0 : 2);
rc = 0;
lc = 0;
}
}
return res + lc;
}
}
性能
