题目描述
思路解析动画文字版
记住「bal 记盈亏、need 记最深亏空、答案 = (need+1)/2」,下面每一帧都在套它。
开局:bal 记当前「左括号 减 右括号」的差,need 记一路见过的最深亏空。从第 0 个字符开始扫。
第 0 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
这个右括号没人接住,标红压入亏空堆;此刻 bal = -1,亏空创新深,need 刷新为 1。
第 1 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
这个右括号没人接住,标红压入亏空堆;此刻 bal = -2,亏空创新深,need 刷新为 2。
第 2 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -1。
第 3 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
这个右括号没人接住,标红压入亏空堆;此刻 bal = -2,还没到最深,need 仍是 2。
第 4 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
这个右括号没人接住,标红压入亏空堆;此刻 bal = -3,亏空创新深,need 刷新为 3。
第 5 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -2。
第 6 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
这个右括号没人接住,标红压入亏空堆;此刻 bal = -3,还没到最深,need 仍是 3。
第 7 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -2。
第 8 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -1。
第 9 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 +0。
整条路上最深亏空是 3(某一刻同时堆了 3 个未匹配右括号)。原串还没合法,但已经知道:每次交换能消两层失衡,所以 (3+1)/2 向下取整 = 2 次交换就够把全串变合法。
边界先想清:已平衡为 0;最浅的一处失衡也要 1 次;need 越深、次数越多。
两个高频追问:一次修两层 与 栈可降维成一个计数器。
参考代码
class Solution: def minSwaps(self, s: str) -> int: balance = 0 need = 0 for ch in s: balance += 1 if ch == '[' else -1 need = max(need, -balance) return (need + 1) // 2复杂度
- 时间：O(n)，从头到尾扫一遍字符串
- 空间：O(1)，只用 bal、need 两个整数变量
易错点
面试追问把动画讲成自己的话
追问为什么一次交换能消掉「两层」失衡,而不是一层?
追问这题为什么贴「栈」标签却可以不用栈?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符串的最优划分
LeetCode 2405 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题