题目描述
给你一个括号字符串 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 只包含 ‘(‘ 和 ‘)’ 。
算法1
(贪心)
- 先扫描一遍,碰到字符为’(‘,就res++,如果碰到了字符为’)’
- 如果当前下标的前一个也为’)’,则res–
- 如果不符合上一个条件,则需要操作一下,并且下标加一
- 最后如果res不为0,则需要在操作次数加上res*2
Java 代码
class Solution {
public int minInsertions(String s) {
int n=s.length(),sum=0,res=0;
for(int i=0;i<n;i++){
if(s.charAt(i)=='('){
res++;
}else{
if(i+1<n&&s.charAt(i+1)==')'){
res--;
i++;
}else{
sum++;
res--;
}
if(res<0){
sum++;
res=0;
}
}
if(res<0){
sum++;
res=0;
}
}
return sum+res*2;
}
}