企业官网建设流程全解析

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

力扣题目链接：https://leetcode.cn/problems/minimum-insertions-to-balance-a-parentheses-string/

给你一个括号字符串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只包含'('和')'。

解题方法一：左右括号匹配

类似单个括号匹配《921.使括号有效的最少添加：一次遍历（贪心）》，我们同样使用一个变量diff来统计左括号比未配对右括号多多少个。

遍历一次字符串，遇到左括号则diff++，遇到右括号则需要进行两个操作：

1. 如果有未配对的左括号，则diff--，否则需要补一个左括号，ans++
2. 如果下一个字符还是右括号，则匹配成功，抵消掉并且i++，否则需要补一个右括号，ans++

最终剩下多少个左括号就需要补充二倍数量的右括号，ans += diff * 2。

• 时间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))
• 空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-10-09 10:59:38 */classSolution{public:intminInsertions(conststring&s){intans=0;intdiff=0;for(size_t i=0,n=s.size();i<n;i++){if(s[i]=='('){diff++;}else{if(diff){diff--;}else{ans++;}if(i+1<n&&s[i+1]==')'){i++;}else{ans++;}}}returnans+diff*2;}};

Java

/* * @LastEditTime: 2026-10-09 11:22:03 */classSolution{publicintminInsertions(Strings){intans=0;intdiff=0;for(inti=0;i<s.length();i++){if(s.charAt(i)=='('){diff++;}else{if(diff>0){diff--;}else{ans++;}if(i+1<s.length()&&s.charAt(i+1)==')'){i++;}else{ans++;}}}returnans+diff*2;}}

Go

/* * @LastEditTime: 2026-10-09 11:19:46 */packagemainfuncminInsertions(sstring)(ansint){diff:=0fori:=0;i<len(s);i++{ifs[i]=='('{diff++}else{ifdiff>0{diff--}else{ans++}ifi+1<len(s)&&s[i+1]==')'{i++}else{ans++}}}returnans+diff*2}

Python

Python没有for(;😉，使用while记得i++。

''' LastEditTime: 2026-10-10 09:39:02 '''classSolution:defminInsertions(self,s:str)->int:ans=diff=i=0n=len(s)whilei<n:ifs[i]=='(':diff+=1else:ifdiff:diff-=1else:ans+=1ifi+1<nands[i+1]==')':i+=1else:ans+=1i+=1returnans+diff*2

解题方法二：不要看了，屎山代码

记录未匹配的左括号和右括号数量。

如果遇到左括号，left++，补全未配对的右括号：

1. 若右括号为奇数个，先补上一个
2. 抵消掉能抵消的括号
3. 如果右括号还有剩余，则补上对应数量一半的左括号

如果遇到右括号，right++：

1. 如果左括号已经不够抵消右括号，则补上所需左括号
2. 抵消掉能抵消的括号

相当于遇到右括号就看有无左括号，有就存一个或者直接抵消掉，没有就补上左括号；遇到左括号就清算右括号

• 时间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))
• 空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-10-09 09:51:51 */classSolution{private:intmeetLeft(int&left,int&right){intans=0;if(right%2){right++;ans++;}intloss=min(left,right/2);left-=loss;right-=loss*2;ans+=right/2;right=0;returnans;}intmeetRight(int&left,int&right){intans=0;if((right+1)/2>left){ans+=(right+1)/2;left=(right+1)/2;}intloss=min(left,right/2);left-=loss;right-=loss*2;returnans;}public:intminInsertions(conststring&s){intans=0;intleft=0,right=0;for(charc:s){if(c=='('){ans+=meetLeft(++left,right);}else{ans+=meetRight(left,++right);}}ans+=meetLeft(left,right);ans+=left*2;returnans;}};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源