因为括号可以在任何地方插入，我们在意的主要就是左括号和右括号分别多出了多少。因此对左括号先进行计数，右括号出现时先抵消左括号，如果左括号抵消完了说明右括号有多的，反之则左括号有多的；如果二者皆为 0 则不需要补充。
class Solution { public: int minAddToMakeValid(string s) { // 注意括号可以在任何位置插入 // 主要就看有多少左括号和右括号没有被抵消 int left = 0, right = 0; for (char c : s) { if (c == '(') { left++; } else { if (left > 0) { // 还有左括号就抵消 left--; } else { // 没有左括号了，右括号多了 right++; } } } return left + right; } };
同上，最优的贪心解法：时间 O(n)，空间 O(1)
O(n)
O(1)
class Solution { public: int minAddToMakeValid(string s) { int ans = 0; int balance = 0; for (char c: s) { if (c == '(') { balance++; } else { if (balance == 0) { ans++; } else { balance--; } } } return ans + balance; } };
咪帕 10-06 10:101楼