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

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

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题还是括号匹配问题，但需要注意两个点。第一点就是遇到一个左括号后，对右括号的需求量增加2，第二点就是碰到一个左括号后，如果右括号的数量是奇数个，那么我们需要添加一个左括号，并对右括号的需求减一以保证一个左括号对应两个右括号。

具体代码如下：

class Solution {
    public int minInsertions(String s) {
        int insertCount = 0;
        int needNums = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                needNums += 2;
                if (needNums % 2 == 1) {
                    insertCount++;
                    needNums--;
                }
            }

            if (s.charAt(i) == ')') {
                needNums--;
                if (needNums == -1) {
                    needNums = 1;
                    insertCount++;
                }
            }
        }
        return insertCount + needNums;
    }
}