【贪心, 模拟栈】使括号有效的最少添加

题目

921. 使括号有效的最少添加

---

只有满足下面几点之一，括号字符串才是有效的：

• 它是一个空字符串，或者
• 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
• 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。

• 例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

返回 为使结果字符串 s 有效而必须添加的最少括号数。

示例 1：

输入：s = "())"
输出：1

示例 2：

输入：s = "((("
输出：3

提示：

• 1 <= s.length <= 1000
• s 只包含 '(' 和 ')' 字符。

解题

方法一：贪心 模拟栈

思路

既然要使 s 有效且还要添加最少的括号，那么我们可以在且仅在括号序列无效的时候添加括号。

具体来说：维护一个栈，遍历字符串中每个字符，如果当前字符是左括号就入栈，如果是右括号就出栈，但如果当前字符是右括号需要出栈的时候栈已经为空了，就说明左边已经没有可以和它匹配的左括号了，这时需要添加一个左括号(++require)。
那么如果右括号没了怎么办？如果右括号没了不会出现栈空的情况，但是在字符串遍历完成后没匹配右括号的左括号都会留在栈中，也就是说，此时栈的大小就是最少需要添加的右括号的数量。
这样下来，require + stk.size() 就是我们要求的答案。

我们注意到，字符串中只会存在一种括号（ ( 或 )）所以我们不必真的去维护一个栈，而是使用一个计数(cnt)来表示栈目前的大小就可以了。

代码

class Solution {
    public int minAddToMakeValid(String s) {
        int require = 0, cnt = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(') ++cnt;
            else if (cnt > 0) --cnt;
            else ++require;
        }
        return require + cnt;
    }
}