使字符串平衡的最小交换次数 图解题解
这道题到底在问什么
- 输入
- s = "][]["
- 输出
- 1 (交换两端,变成 "[][]")
- 输入
- s = "]]][[["
- 输出
- 2 (最深失衡为 3,需要 2 次)
- 输入
- s = "[]"
- 输出
- 0 (已经平衡)
最优解：一步一步想明白
- 3记住「bal 记盈亏、need 记最深亏空、答案 = (need+1)/2」,下面每一帧都在套它。
- 4开局:bal 记当前「左括号 减 右括号」的差,need 记一路见过的最深亏空。从第 0 个字符开始扫。
- 5第 0 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
- 6这个右括号没人接住,标红压入亏空堆;此刻 bal = -1,亏空创新深,need 刷新为 1。
- 7第 1 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
- 8这个右括号没人接住,标红压入亏空堆;此刻 bal = -2,亏空创新深,need 刷新为 2。
- 9第 2 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
- 10这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -1。
- 11第 3 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
- 12这个右括号没人接住,标红压入亏空堆;此刻 bal = -2,还没到最深,need 仍是 2。
- 13第 4 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
- 14这个右括号没人接住,标红压入亏空堆;此刻 bal = -3,亏空创新深,need 刷新为 3。
- 15第 5 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
- 16这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -2。
- 17第 6 个是右括号 ],此刻没有可用的左括号在它前面接住它,bal 即将减一。
- 18这个右括号没人接住,标红压入亏空堆;此刻 bal = -3,还没到最深,need 仍是 3。
- 19第 7 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
- 20这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -2。
- 21第 8 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
- 22这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 -1。
- 23第 9 个是左括号 [,它能去抵消一层之前堆积的亏空,bal 即将加一。
- 24这个左括号把红色亏空堆里最上面一层抵消掉(注意只是计数抵消,不是原序里的合法括号对),亏空减一,bal 回升到 +0。
- 25整条路上最深亏空是 3(某一刻同时堆了 3 个未匹配右括号)。原串还没合法,但已经知道:每次交换能消两层失衡,所以 (3+1)/2 向下取整 = 2 次交换就够把全串变合法。
⚠️ 容易写错的地方
✗ 错：真去枚举模拟每一次交换
✓ 对：只统计最深亏空 need
交换有 O(n²) 种,贪心一遍扫即可,只关心「同时堆叠的未匹配右括号最多几个」
✗ 错：答案写成 need 本身
✓ 对：答案是 (need + 1) / 2 向下取整
一次交换能同时修正最外两层失衡,所以要除以 2;need 为奇数时 +1 再除
✗ 错：把 bal 直接当答案
✓ 对：bal 是实时盈亏,need 才是峰值亏空
末尾 bal 一定回到 0(左右数量相等),真正决定次数的是过程中最深的负值
完整代码（Python / C++ / Java）
Python
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) // 2C++
#include <string>
using namespace std;
class Solution {
public:
int minSwaps(string s) {
int bal = 0, need = 0;
for (char c : s) {
bal += c == '[' ? 1 : -1;
need = max(need, -bal);
}
return (need + 1) / 2;
}
};Java
import java.util.*;
class Solution {
public int minSwaps(String s) {
int bal = 0, need = 0;
for (char c : s.toCharArray()) {
bal += c == '[' ? 1 : -1;
need = Math.max(need, -bal);
}
return (need + 1) / 2;
}
}复杂度
时间
O(n)
从头到尾扫一遍字符串
空间
O(1)
只用 bal、need 两个整数变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使字符串平衡的最小交换次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么一次交换能消掉「两层」失衡,而不是一层?+
把最靠前的一个未匹配右括号 ] 和最靠后的一个未匹配左括号 [ 对调,原来开头多出来的 ] 变成 [、结尾多出来的 [ 变成 ],一来一回同时修好了最外侧的两处失衡,因此 need 层失衡只需约一半次数,即 (need+1)/2。
这题为什么贴「栈」标签却可以不用栈?+
本题不需要真维护栈,核心量只有两个:bal 等于「当前左括号数 减 右括号数」,也就是扫到此处的前缀余额;need 记录这条路上前缀余额最负值的相反数,也就是某一刻同时堆积的未匹配右括号最多有几个。若一定要用栈类比,要明确这是一个「亏空栈」(存的是没人接住的右括号,不是经典做法里剩的左括号):遇 ] 且前面没有可用 [ 接住它时,这个右括号压入亏空栈;遇 [ 就弹掉一层亏空。need 就是这个亏空栈到达过的最大深度,而它恰好等于 -bal 的最大值。所以一个整数 bal 就能代替整个栈,空间从 O(n) 降到 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使字符串平衡的最小交换次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。