921. 使括号有效的最少添加
题目描述
输入字符串 s，只由 '(' 和 ')' 组成。
有效括号串的定义：空串有效；两个有效串拼接后有效；在一个有效串外面套一对 () 后也有效。
每次操作可以在 s 的任意位置插入一个 '(' 或一个 ')'。返回让 s 变成有效括号串所需的最少插入次数。
示例 1
输入：s = "())" 输出：1
解释：末尾多出一个 )，补一个 ( 即可。
示例 2
输入：s = "((("
输出：3解释：三个 ( 都没有配对，需要补三个 )。
数据范围
1 <= s.length <= 1000s中只有'('和')'两种字符。
解题思路
用一个计数器 bal 代替栈，记录还没配对的左括号数。遇到 ( 就 bal+1；遇到 ) 时若有未配对的左括号就消掉一个，否则这个 ) 无论如何都缺一个左括号，ans+1。扫描结束后剩下的 bal 个左括号各缺一个右括号，答案是 ans + bal。
为什么正确
扫描完前缀后，bal 是前缀中未配对的 ( 个数，ans 是前缀中必然无法配对的 ) 个数。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
只统计左右括号数量之差是错的：")(" 两种括号数量相等，答案却是 2。必须按顺序配对，右括号只能和它左边的左括号配对。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minAddToMakeValid(self, s: str) -> int:
ans = bal = 0
for c in s:
if c == '(':
bal += 1
elif bal > 0:
bal -= 1
else:
ans += 1
return ans + balclass Solution {
public int minAddToMakeValid(String s) {
int ans = 0, bal = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
bal++;
} else if (bal > 0) {
bal--;
} else {
ans++;
}
}
return ans + bal;
}
}class Solution {
public:
int minAddToMakeValid(string s) {
int ans = 0, bal = 0;
for (char c : s) {
if (c == '(') {
bal++;
} else if (bal > 0) {
bal--;
} else {
ans++;
}
}
return ans + bal;
}
};func minAddToMakeValid(s string) int {
ans, bal := 0, 0
for _, c := range s {
if c == '(' {
bal++
} else if bal > 0 {
bal--
} else {
ans++
}
}
return ans + bal
}var minAddToMakeValid = function(s) {
let ans = 0, bal = 0;
for (const c of s) {
if (c === '(') {
bal++;
} else if (bal > 0) {
bal--;
} else {
ans++;
}
}
return ans + bal;
};function minAddToMakeValid(s: string): number {
let ans = 0, bal = 0;
for (const c of s) {
if (c === '(') {
bal++;
} else if (bal > 0) {
bal--;
} else {
ans++;
}
}
return ans + bal;
}