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

记牢这套:x 记欠债的左括号、ans 记插入次数;遇 ")" 先凑 "))" 再还债,扫完每个剩下的 "(" 补两个 ")"。下面每帧都在套它。

总览 · 两个计数器清零,从最左开扫：上面这排是 "(()))((" 拆开的 7 个字符,前面像普通括号,后面跟着三个连续的右括号又接两个左括号。开扫前两个计数器都清零:x 记还欠 "))" 的左括号有几个,ans 记插入次数。从最左第 0 位往右扫。

读第 0 个 · "("：第 0 位是 "(",一个左括号要靠连续两个右括号 "))" 来配。先把它记成一笔欠债。

记一笔欠债 · x 加到 1：x 加一变成 1,表示现在有 1 个左括号在等它的 "))"。这位处理完变蓝,继续往右。

读第 1 个 · "("：第 1 位又是 "(",再记一笔欠债。

记一笔欠债 · x 加到 2：x 加到 2,现在有两个左括号在排队等各自的 "))"。

读第 2 个 · ")"：第 2 位是 ")"。遇到右括号先别急,得看它后面有没有搭档 ")",能凑成 "))" 才好去还一笔债。

看第 3 位 · 也是 ")"：看第 3 位,正好也是 ")"。第 2、3 位连成一个现成的 "))",这一对不用插任何东西。

收下这对 "))" · 跨过两位：把这对现成的 "))" 收下,两位一起用掉,下标直接跨过第 2、3 两位。

还掉一笔债 · x 减到 1：这对 "))" 去还一笔欠债,x 从 2 减到 1。注意 x 只是个数字,记还欠几笔,不必管具体配的是哪个左括号。

读第 4 个 · ")"：跳到第 4 位,又是 ")"。老规矩,先看它后面有没有搭档来凑 "))"。

看第 5 位 · 是 "(" 不是 ")"：第 5 位是 "(" 不是 ")",这个右括号落单了,自己配不成 "))"。把它标红,得想办法补。

插一个 ")" 补成 "))" · ans 加到 1：那就插入一个 ")" 给它补成 "))",ans 加一变成 1。这是这一趟里第一次真正的插入。

还掉一笔债 · x 减到 0：补成的这对 "))" 去还债,x 从 1 减到 0,前面排队的左括号暂时都还清了。第 4 位处理完变蓝。

读第 5 个 · "("：第 5 位是 "(",又来一笔新欠债。

记一笔欠债 · x 加到 1：x 从 0 加到 1,这个左括号开始等它的 "))"。

读第 6 个 · "("：第 6 位还是 "(",再记一笔欠债。

记一笔欠债 · x 加到 2：x 加到 2。这已经是最后一个字符了,可整串扫完,这两个左括号还没等到自己的 "))"。

扫描完毕 · 进入收尾：7 个字符全部扫过一遍,都变蓝了。现在进入收尾阶段,专门处理还没配上 "))" 的左括号。

还欠 2 笔 · x 停在 2：看计数器,x 停在 2,标红的这两个左括号(第 5、6 位)还欠着 "))" 没还。

每个补 "))" · ans 加 4 到 5：收尾结算:每个欠债的左括号都要补上连续两个右括号 "))",2 个左括号就是 2 乘 2 等于 4 次插入,ans 从 1 加到 5。

完成 · 答案 5 次：全程一共插了 5 次:中间给落单的 ")" 补了 1 个,结尾给两个没配上的 "(" 各补 "))" 共 4 个。加起来就是 5,答案站得住。

边界三例:"())" 已平衡插 0 次;全是 "(" 时每个补 "))";全是 ")" 时既要补 "(" 又要给落单的补 ")"。

面试重点:平衡定义是一配二、"))" 缺左括号要补 "("、时间 O(n) 空间 O(1)。