LeetCode 题解工作台
平衡括号字符串的最少插入次数
给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足： 任何左括号 '(' 必须对应两个连续的右括号 '))' 。 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。 比方说 "())" ， "())(())))" 和 "(())())))" 都…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们用 表示字符串中待匹配的左括号的数量，初始时为 。遍历字符串 ： 如果遇到左括号，则 的值加 ；如果遇到右括号，我们分情况讨论：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
- 任何左括号
'('必须对应两个连续的右括号'))'。 - 左括号
'('必须在对应的连续两个右括号'))'之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
输入：s = "(()))" 输出：1 解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：
输入：s = "())" 输出：0 解释：字符串已经平衡了。
示例 3：
输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：
输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：
输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
提示：
1 <= s.length <= 10^5s只包含'('和')'。
解题思路
方法一：贪心
我们用 表示字符串中待匹配的左括号的数量，初始时为 。遍历字符串 ：
如果遇到左括号，则 的值加 ；如果遇到右括号，我们分情况讨论：
- 如果有两个连续的右括号，那么我们先让指针往后移动一位；否则，我们需要插入一个右括号，使得出现两个连续的右括号，因此插入次数加 ；
- 如果 ，说明当前没有待匹配的左括号，我们需要插入一个左括号，用于匹配上面准备好的两个连续的右括号，因此插入次数加 ；否则，我们让 的值减 。
然后指针往后移动一位，继续下一次遍历。
遍历结束后，如果 ，说明字符串已经平衡，返回插入次数；否则，说明字符串中有待匹配的左括号，我们需要再插入 个右括号，使得字符串变成平衡字符串，返回插入次数。
时间复杂度 ，空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each character is processed once, and stack operations are O(1). Space complexity is O(n) in the worst case to store all '(' in the stack. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect clarity in handling unmatched ')' with the double-close requirement.
- question_mark
Watch for correct greedy insertions rather than global balancing attempts.
- question_mark
Check understanding of stack usage to maintain state efficiently.
常见陷阱
外企场景- error
Forgetting that each '(' requires exactly two ')' for a match, not one.
- error
Not treating a lone ')' as needing an extra insertion immediately.
- error
Attempting to rebalance from the end instead of processing left to right.
进阶变体
外企场景- arrow_right_alt
Input strings with only '(' or only ')' to test extreme insertions.
- arrow_right_alt
Strings with nested patterns like '((()))))' to verify stack handling.
- arrow_right_alt
Alternating parentheses such as '())(()))(' to stress greedy insertion logic.