921. 使括号有效的最少添加：简单贪心思想

题目描述

这是 力扣上的 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）

今天就到这里，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~