题目重点：只插入、不删除、不重排，最后补足未闭合左括号。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入仅(和)，要求通常的括号匹配：任意前缀左数≥右数，最终相等。
- 每次插入任意单个括号，返回最少数量。
解题路线
- 维护未匹配左括号balance。遇(加1；遇)且balance>0则配掉一个。
- 遇)且balance=0，原前缀无法靠未来括号修复，必须在它前面插一个(，因此该操作为必要下界。
- 结束剩balance个左括号必须各补一个)，同样必要。算法只做这些必要修复，因此达到下界。
手动走一遍
输入())(：第三个)需要补(，尾部(需要补)，总2。)))需要前置三个(；空串0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def min_insertions(s):
balance = inserted = 0
for c in s:
if c == '(':
balance += 1
elif c == ')':
if balance:
balance -= 1
else:
inserted += 1
else:
raise ValueError("parentheses only")
return inserted + balance
复杂度
O(n)时间、O(1)空间。生成结果字符串另需O(n+answer)。
易错点与追问
容易失分的边界
- 不要遇到无匹配)就把balance减到负数然后只看最终绝对值。
- 若规则一个(须配两个))，状态和最优修复不同。
继续深挖
- 若插入/删除费用不同，贪心的必要性还成立吗？
- 如何返回一种实际修复字符串及插入位置？
