使括号有效的最少添加

遇 ( 就 open+1(攒着等右括号);遇 ) 先看手里有没有 ( 能配——有就 open−1(配掉),没有就 need+1(这个 ) 注定要补一个 ( )。

下面拿 "()))((" 一格一格演。盯住屏幕下方的 open 和 need 两个数怎么随指针变化。

起步 · 指针落在第 0 位：字符串 "()))((" 摊成 6 格。指针停在第 0 位,两个计数器都从 0 起步。

第 0 位 = ( · open+1：第 0 位是 (,把它攒进手里:open 从 0 变 1。它在等右边出现一个 ) 来配对。

指针 → 第 1 位：第 0 位处理完(变灰),指针挪到第 1 位。手里还攒着 1 个没配对的 (。

第 1 位 = ) · 配掉一对：第 1 位是 ),而手里正好有 1 个 (。配对成功:open 减回 0。这两格(绿)就是已经合法的一对。

指针 → 第 2 位：前两格配成一对,封存变灰。指针到第 2 位。注意现在 open=0——手里没有空闲的 ( 了。

第 2 位 = ) · 没得配!：第 2 位又是 ),可手里 open=0,没有 ( 能配它!这个孤儿 ) 只能记账:need 从 0 变 1,将来必须给它补一个 (。

指针 → 第 3 位：第 2 位那个孤儿 ) 记完账(标红),指针到第 3 位。现在 need=1:已经欠了 1 个左括号。

第 3 位 = ) · 又没得配：第 3 位还是 ),open 依旧是 0,又一个孤儿!need 从 1 变 2。现在欠了 2 个左括号。

指针 → 第 4 位：两个孤儿 ) 都记账了(标红),need 累到 2。指针到第 4 位,接下来是两个 (。

第 4 位 = ( · open+1：第 4 位是 (,攒进手里:open 从 0 变 1。它在等右边的 ) 来配,可惜后面没有了——先记着。

指针 → 第 5 位：指针到最后第 5 位。手里攒着 1 个没配对的 (,欠债 need 仍是 2。

第 5 位 = ( · open+1：第 5 位还是 (,再攒一个:open 从 1 变 2。这两个 ((都没有右括号能配,扫完后它们就是「余量」。

扫描结束 · 结算：6 格全扫完。结算:手里余下 open=2 个左括号(绿,各缺一个 ))、need=2 个孤儿右括号(红,各缺一个 ()。

答案 = need + open：把两笔账加起来:欠的 2 个 ( 要补、余的 2 个 ) 也要补,一共补 4 个,字符串才合法。答案就是 4。

再演一例 · s = "(()" 起步：换 "(()" 再走一遍,这次专看雷区②说的结尾余下 open。指针停在第 0 位,计数器归零。

第 0 位 = ( · open+1：第 0 位 (,攒进手里:open = 1。

第 1 位 = ( · open+1：第 1 位又是 (,再攒一个:open = 2。手里现在攒着两个左括号。

第 2 位 = ) · 配掉一对：第 2 位 ),手里有 ( 可配,配掉一对:open 从 2 减到 1。全程没出现孤儿,need 一直是 0。

"(()" 结算 · 答案 1：结算:余下 1 个没配对的 (((第 0 位,标灰),它缺一个 ),所以补 1 个就合法,答案 1。验证了「结尾余下的 open 也要补」。

孤儿 ) 总出现在余下 ( 的左边(位置 2、3 在 4、5 之前),所以一个补在左、一个补在右,谁也救不了谁,只能各补各的——这正是 need+open 不能再少的原因。

雷区实演 · 忘加 open：拿 "(((" 试:全是 (,没有任何孤儿 ),need 一直是 0。要是只返回 need 就得 0——大错!其实 3 个 ( 各缺一个 ),必须补 3 个。这就是为什么结尾要加 open。

边界三连：先想空串(0)、纯左括号(只靠 open)、左右都缺(need+open)三种,代码就稳了。

面试追问：把「为何相加不抵消」和「栈与计数等价」讲清楚,是这题面试的得分点。