题目描述
这是 力扣上的 921. 使括号有效的最少添加，难度为 中等。
题目分析
题目描述和题目示例我们知道这又是一个处理括号的题目，一般咱们处理括号类型的题目都会习惯性的使用栈的方式，例如补充缺失的括号等等
一开始看到这个题，我的第一想法也是使用栈，因为栈的先入后出的特性，这就保证了咱们的括号的有序和成对
但是仔细看题目给出的示例，题目只要要求我们使用最少添加括号的方式，来实现本题的要求，那么其实我们只需要检查有多少左括号有右括号就可以知道答案了，但是这里我们需要注意的是，就现成给出的字符串中，左括号一定要在右括号之前，才可以成对，否则就是不能成对的
此处咱们就可以有这样的思路
- 遍历题目给出的字符串，如果是左括号，就记录下来左括号的数量 leftCnt，如果是右括号的话，咱们就看看 leftCnt 是否大于 0
- 若是，则说明可以成对，则 leftCnt-1
- 若不是，则说明，此时的右括号没有现成的匹配的左括号，那么就需要我们主动加上一个左括号， 那么就结果 res +1
- 遍历完毕之后，咱们就可以检查 结果 res 与 leftCnt 的和，即时本题需要咱们添加最少的括号个数，此处并没有要求我们记录是需要添加左括号还是由括号
- 如果需要的话，咱们的本次做法也是可以的， leftCnt 表示需要添加的右括号个数，res 表示需要添加左括号的个数
实现方式，同样咱们还是分为 golang 和 C 语言的方式，本次 golang 和 C 的实现没有什么不同：
Golang 的实现方式：
func minAddToMakeValid(s string) (res int) { leftCnt := 0 for _, c := range s { if c == '(' { leftCnt++ } else if leftCnt > 0 { leftCnt-- } else { res++ } } return res + leftCnt }
C 的实现方式：
int minAddToMakeValid(char * s){ int res = 0; int leftCnt = 0; int length = strlen(s); for (int i = 0; i < length; i++) { char c = s[i]; if (c == '(') { leftCnt++; } else if(leftCnt > 0) { leftCnt--; }else { res++; } } res += leftCnt; return res; }
ini
复制代码
int minAddToMakeValid(char * s){ int res = 0; int leftCnt = 0; int length = strlen(s); for (int i = 0; i < length; i++) { char c = s[i]; if (c == '(') { leftCnt++; } else if(leftCnt > 0) { leftCnt--; }else { res++; } } res += leftCnt; return res;}这种实现方式，时间复杂度是 O(n)，n 就是遍历 s 字符串中字符的个数，空间复杂度是 O(1）
今天就到这里，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
