1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minAddToMakeValid(String s) {
        int leftParenCount = 0, moves = 0;
        char[] sArray = s.toCharArray();
        for (char c : sArray) {
            if (c == '(') {
                leftParenCount += 1;
            } else {
                if (leftParenCount == 0) {
                    moves += 1;
                } else {
                    leftParenCount -= 1;
                }
            }
        }
        return moves + leftParenCount;
    }
}

记录左括号的个数即可.

时间复杂度: O(n)
空间复杂度: O(1)