题目描述

给定一个括号字符串 s，它只包含字符 '(' 和 ')'。一个括号字符串被称为平衡的当它满足：

• 任何左括号 '(' 必须对应两个连续的右括号 '))'。
• 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"，"())(())))" 和 "(())())))" 都是平衡的，")()"，"()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s平衡的最少插入次数。

样例

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。
我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

输入：s = "())"
输出：0
解释：字符串已经平衡了。

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '('。

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))"。

限制

• 1 <= s.length <= 10^5
• s 只包含 '(' 和 ')'。

算法

(分类讨论) $O(n)$

1. 维护一个统计值 $v$，初始值为 0，( 价值为 2，) 价值为 1。然后遍历字符串。
2. 如果遇到 (
   • 如果 $v > 0$ 且 $v$ 是奇数，则说明之前需要补一个 )，然后 $v$ 减 1。
   • 如果 $v < 0$，则说明缺 (，至少缺 $-v / 2$ 个 (。
     • 在这个情况下，如果 $v$ 仍然是奇数，则说明有一个落单的 )，需要一个额外的 ( 和 )。
     • $v$ 置 0。
3. 如果遇到 )，则 $v$ 自减 1。
4. 遍历结束后，如果 $v > 0$，则说明需要补 $v$ 个 ‘)’；否则，按照之前 $v < 0$ 补全括号。

时间复杂度

• 遍历字符串一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

Go 代码

func minInsertions(s string) int {
    var v, ans int
    for _, c := range s {
        if c == '(' {
            if v > 0 {
                if v % 2 == 1 {
                    ans++
                    v--
                }
            } else {
                ans += -v / 2
                if v % 2 == -1 {
                    ans += 2
                }
                v = 0
            }
            v += 2
        } else {
            v--
        }
    }

    if v > 0 {
        ans += v
    } else {
        ans += -v / 2
        if v % 2 == -1 {
            ans += 2
        }
    }

    return ans
}