1541.平衡括号字符串的最少插入次数：一次遍历

【LetMeFly】1541.平衡括号字符串的最少插入次数：一次遍历

力扣题目链接：https://leetcode.cn/problems/minimum-insertions-to-balance-a-parentheses-string/

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

• 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
• 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

 

示例 1：

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。

示例 3：

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。

示例 4：

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。

示例 5：

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。

 

提示：

• 1 <= s.length <= 10^5
• s 只包含 '(' 和 ')' 。

解题方法一：左右括号匹配

类似单个括号匹配《921.使括号有效的最少添加：一次遍历（贪心）》，我们同样使用一个变量diff来统计左括号比未配对右括号多多少个。

遍历一次字符串，遇到左括号则diff++，遇到右括号则需要进行两个操作：

1. 如果有未配对的左括号，则diff--，否则需要补一个左括号，ans++
2. 如果下一个字符还是右括号，则匹配成功，抵消掉并且i++，否则需要补一个右括号，ans++

最终剩下多少个左括号就需要补充二倍数量的右括号，ans += diff * 2。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-10-09 10:59:38
 */
class Solution {
public:
    int minInsertions(const string& s) {
        int ans = 0;
        int diff = 0;
        for (size_t i = 0, n = s.size(); i < n; i++) {
            if (s[i] == '(') {
                diff++;
            } else {
                if (diff) {
                    diff--;
                } else {
                    ans++;
                }
                if (i + 1 < n && s[i + 1] == ')') {
                    i++;
                } else {
                    ans++;
                }
            }
        }
        return ans + diff * 2;
    }
};

Java

/*
 * @LastEditTime: 2026-10-09 11:22:03
 */
class Solution {
    public int minInsertions(String s) {
        int ans = 0;
        int diff = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                diff++;
            } else {
                if (diff > 0) {
                    diff--;
                } else {
                    ans++;
                }
                if (i + 1 < s.length() && s.charAt(i + 1) == ')') {
                    i++;
                } else {
                    ans++;
                }
            }
        }
        return ans + diff * 2;
    }
}

Go

/*
 * @LastEditTime: 2026-10-09 11:19:46
 */
package main

func minInsertions(s string) (ans int) {
    diff := 0
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            diff++
        } else {
            if diff > 0 {
                diff--
            } else {
                ans++
            }
            if i + 1 < len(s) && s[i + 1] == ')' {
                i++
            } else {
                ans++
            }
        }
    }
    return ans + diff * 2
}

Python

Python没有for(;;)，使用while记得i++。

'''
LastEditTime: 2026-10-10 09:39:02
'''
class Solution:
    def minInsertions(self, s: str) -> int:
        ans = diff = i = 0
        n = len(s)
        while i < n:
            if s[i] == '(':
                diff += 1
            else:
                if diff:
                    diff -= 1
                else:
                    ans += 1
                if i + 1 < n and s[i + 1] == ')':
                    i += 1
                else:
                    ans += 1
            i += 1
        return ans + diff * 2

解题方法二：不要看了，屎山代码

记录未匹配的左括号和右括号数量。

如果遇到左括号，left++，补全未配对的右括号：

1. 若右括号为奇数个，先补上一个
2. 抵消掉能抵消的括号
3. 如果右括号还有剩余，则补上对应数量一半的左括号

如果遇到右括号，right++：

1. 如果左括号已经不够抵消右括号，则补上所需左括号
2. 抵消掉能抵消的括号

相当于遇到右括号就看有无左括号，有就存一个或者直接抵消掉，没有就补上左括号；遇到左括号就清算右括号

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-10-09 09:51:51
 */
class Solution {
private:
    int meetLeft(int& left, int& right) {
        int ans = 0;
        if (right % 2) {
            right++;
            ans++;
        }
        int loss = min(left, right / 2);
        left -= loss;
        right -= loss * 2;
        ans += right / 2;
        right = 0;
        return ans;
    }

    int meetRight(int& left, int& right) {
        int ans = 0;
        if ((right + 1) / 2 > left) {
            ans += (right + 1) / 2;
            left = (right + 1) / 2;
        }
        int loss = min(left, right / 2);
        left -= loss;
        right -= loss * 2;
        return ans;
    }
public:
    int minInsertions(const string& s) {
        int ans = 0;
        int left = 0, right = 0;
        for (char c : s) {
            if (c == '(') {
                ans += meetLeft(++left, right);
            } else {
                ans += meetRight(left, ++right);
            }
        }
        ans += meetLeft(left, right);
        ans += left * 2;
        return ans;
    }
};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源