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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 思路

Stack

# 解法

class Solution {
    public int minInsertions(String s) {
        int count = 0;
        Stack<Character> stk = new Stack<>();
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stk.push('(');
            }else if(s.charAt(i)==')'&&i+1<s.length()&&s.charAt(i+1)==')'){
                if(stk.isEmpty()){
                    count++;
                    i++;
                }else{
                    stk.pop();
                    i++;
                }
            }else{
                count++;
                if(stk.isEmpty()){
                    count++;
                }else{
                    stk.pop();
                }
            }
        }
        if(!stk.isEmpty()){
            int rest = stk.size();
            count += rest * 2;
        }
        return count;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 总结

分析出几种情况，然后分别对各个情况实现

#Java