leetcode921.使括号有效的最少添加（中等）

思路一：栈，栈中最后的元素就是未匹配的个数

class Solution {
public:
    int minAddToMakeValid(string s) {
        
        stack<char> stk;
        for (auto& ch : s) {
            if (ch == '(') stk.push(ch);
            else if (!stk.empty() && stk.top() == '(') stk.pop();
            else stk.push(ch);
        }
        return stk.size();
    }
};

思路二：碰到一个右括号，就补一个左括号
细节：
‘(’ ：+1 ‘)’：-1
如果为-1 ans++; cnt=0
ans+cnt为最后的结果

class Solution {
public:
    int minAddToMakeValid(string s) {
        
        int ans = 0, cnt = 0;
        for (auto& ch : s) {
            if (ch == '(') cnt++;
            else cnt--;
            if (cnt == -1) {
                ans++;
                cnt = 0;
            }
        }
        return ans + cnt;
    }
};