平衡括号字符串的最少插入次数 图解题解

这道题到底在问什么

输入

s = "(()))"

输出

1

输入

s = "(((((("

输出

12

输入

本节演示 s = "(()))(("

输出

5

最优解：一步一步想明白

1. 3记牢这套:x 记欠债的左括号、ans 记插入次数;遇 ")" 先凑 "))" 再还债,扫完每个剩下的 "(" 补两个 ")"。下面每帧都在套它。
2. 4上面这排是 "(()))((" 拆开的 7 个字符,前面像普通括号,后面跟着三个连续的右括号又接两个左括号。开扫前两个计数器都清零:x 记还欠 "))" 的左括号有几个,ans 记插入次数。从最左第 0 位往右扫。
3. 5第 0 位是 "(",一个左括号要靠连续两个右括号 "))" 来配。先把它记成一笔欠债。
4. 6x 加一变成 1,表示现在有 1 个左括号在等它的 "))"。这位处理完变蓝,继续往右。
5. 7第 1 位又是 "(",再记一笔欠债。
6. 8x 加到 2,现在有两个左括号在排队等各自的 "))"。
7. 9第 2 位是 ")"。遇到右括号先别急,得看它后面有没有搭档 ")",能凑成 "))" 才好去还一笔债。
8. 10看第 3 位,正好也是 ")"。第 2、3 位连成一个现成的 "))",这一对不用插任何东西。
9. 11把这对现成的 "))" 收下,两位一起用掉,下标直接跨过第 2、3 两位。
10. 12这对 "))" 去还一笔欠债,x 从 2 减到 1。注意 x 只是个数字,记还欠几笔,不必管具体配的是哪个左括号。
11. 13跳到第 4 位,又是 ")"。老规矩,先看它后面有没有搭档来凑 "))"。
12. 14第 5 位是 "(" 不是 ")",这个右括号落单了,自己配不成 "))"。把它标红,得想办法补。
13. 15那就插入一个 ")" 给它补成 "))",ans 加一变成 1。这是这一趟里第一次真正的插入。
14. 16补成的这对 "))" 去还债,x 从 1 减到 0,前面排队的左括号暂时都还清了。第 4 位处理完变蓝。
15. 17第 5 位是 "(",又来一笔新欠债。
16. 18x 从 0 加到 1,这个左括号开始等它的 "))"。
17. 19第 6 位还是 "(",再记一笔欠债。
18. 20x 加到 2。这已经是最后一个字符了,可整串扫完,这两个左括号还没等到自己的 "))"。
19. 217 个字符全部扫过一遍,都变蓝了。现在进入收尾阶段,专门处理还没配上 "))" 的左括号。
20. 22看计数器,x 停在 2,标红的这两个左括号(第 5、6 位)还欠着 "))" 没还。
21. 23收尾结算:每个欠债的左括号都要补上连续两个右括号 "))",2 个左括号就是 2 乘 2 等于 4 次插入,ans 从 1 加到 5。
22. 24全程一共插了 5 次:中间给落单的 ")" 补了 1 个,结尾给两个没配上的 "(" 各补 "))" 共 4 个。加起来就是 5,答案站得住。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minInsertions(self, s: str) -> int:
        ans = x = 0
        i, n = 0, len(s)
        while i < n:
            if s[i] == '(':
                # 待匹配的左括号加 1
                x += 1
            else:
                if i < n - 1 and s[i + 1] == ')':
                    # 有连续两个右括号，i 往后移动
                    i += 1
                else:
                    # 只有一个右括号，插入一个
                    ans += 1
                if x == 0:
                    # 无待匹配的左括号，插入一个
                    ans += 1
                else:
                    # 待匹配的左括号减 1
                    x -= 1
            i += 1
        # 遍历结束，仍有待匹配的左括号，说明右括号不足，插入 x << 1 个
        ans += x << 1
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minInsertions(string s) {
        int ans = 0, x = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                ++x;
            } else {
                if (i < n - 1 && s[i + 1] == ')') {
                    ++i;
                } else {
                    ++ans;
                }
                if (x == 0) {
                    ++ans;
                } else {
                    --x;
                }
            }
        }
        ans += x << 1;
        return ans;
    }
};

import java.util.*;
class Solution {
    public int minInsertions(String s) {
        int ans = 0, x = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '(') {
                ++x;
            } else {
                if (i < n - 1 && s.charAt(i + 1) == ')') {
                    ++i;
                } else {
                    ++ans;
                }
                if (x == 0) {
                    ++ans;
                } else {
                    --x;
                }
            }
        }
        ans += x << 1;
        return ans;
    }
}

复杂度

面试官可能追问