LeetCode 1151. 最少交换次数来组合所有的 1
目录
题目描述
题意分析
给一个只含
0和1的数组data，每次操作可以交换任意两个位置的元素，问最少交换多少次能让所有的1变成连续的一段。「任意两个位置」这五个字是全题的钥匙，必须先读出来：它意味着交换不是相邻冒泡，不存在「把一个
1从远处挪过来要付出距离代价」这回事。任何一个位置上的0和任何一个位置上的1，一次操作就能对调。这直接排除了模拟移动过程、按距离累加代价的思路。第二个关键观察藏在「最终形态」里：交换不会改变
1的总数，所以答案状态一定是某个长度恰好等于1的总数的连续区间被1填满，区间外全是0。这就把一个「求最少操作次数」的问题，转化成了「选一个定长区间」的问题——目标区间的长度是题目直接给定的，不是要枚举的自由变量。第三步是把代价算清楚。选定某个目标区间后，区间里已经有的
1不用动；区间里剩下的每个0，都必须和区间外的某个1对调，一次交换正好消灭一个区间内的0并补进一个1。所以代价就等于区间内0的个数，也等于「1的总数减去区间内1的个数」。区间外剩余的1的个数与区间内0的个数必然相等，配对不会有富余或短缺，所以这个代价是可达的。数组长度可以到 $10^5$ 量级，暗示答案要在线性时间内得到，不能对每个候选区间都重新数一遍。
边界：数组里一个
1都没有，或只有一个1，本身就已经是「连续的一段」，答案是0；此时目标区间长度为0或1，定长扫描的逻辑退化，最好单独挡掉。另外要注意本题的数组是线性的，首尾不相接。
解法：固定长度滑动窗口
核心思路
暴力做法是枚举所有长度为
ones的区间起点，每个区间重新数一遍里面有多少个1。区间有 $n - ones + 1$ 个，每个数ones次，最坏情况（1占一半）是 $O(n^2)$，$10^5$ 的规模会超时。瓶颈在于相邻两个区间被重复统计了。观察它们的关系：起点右移一格，区间只丢掉最左边一个元素、补进最右边一个元素，中间那
ones - 1个元素完全没变。既然没变，就没有必要重新遍历。于是维护一个变量
windowOnes表示当前区间内1的个数，右移时执行windowOnes += 新进来的元素、windowOnes -= 出去的元素（因为元素只可能是0或1，加减元素值就等于加减是否为1的判定，省掉一次比较）。每次移动是 $O(1)$。循环不变量写清楚：在处理完下标
right之后，windowOnes恒等于闭区间[right - ones + 1, right]内1的个数（当right < ones - 1时这个区间尚未成形，是从下标0开始的前缀，不参与答案统计）。代码里right >= ones才做减法，正是为了让窗口在成形之前先自然长满，成形之后再保持定长。有了这个不变量，
maxOnes取所有已成形窗口中windowOnes的最大值，最终答案就是ones - maxOnes。注意最大化窗口内的1与最小化交换次数是同一件事，因为ones是常量，二者只差一个减号。
解题步骤
- 先统计全局
1的个数ones。为什么第一步就要它：它同时是「目标窗口的长度」和「答案公式里的被减数」，后面所有逻辑都依赖它，必须先扫一遍拿到。- 特判
ones <= 1直接返回0。为什么：零个或一个1天然已经聚在一起，无需交换；而且ones == 0时窗口长度为0，定长滑窗失去意义，提前挡掉比让它退化更清晰。- 右边界
right从0扫到n - 1，先做加法windowOnes += data[right]。为什么可以直接加元素值：数组只含0和1，元素值本身就是「是不是1」的指示量。- 再做减法：
right >= ones时执行windowOnes -= data[right - ones]。为什么条件是right >= ones而不是right >= ones - 1：窗口长度为ones，当前窗口是[right - ones + 1, right]，被挤出去的是下标right - ones；只有right >= ones时这个下标才非负，写成right >= ones - 1会在第一次就访问data[-1]。- 窗口成形后更新最大值：
right >= ones - 1时maxOnes = max(maxOnes, windowOnes)。为什么要这个门槛：right < ones - 1时窗口还没长到ones长度，它统计出的数字对应的是一个更短的区间，不是合法候选。- 返回
ones - maxOnes。为什么不是maxOnes：maxOnes是窗口里已经就位的1，还缺的那部分才是要交换的次数。以
data = [1, 0, 1, 0, 1]走一遍。先统计得ones = 3，所以目标是找一个长度为 3 的窗口，让窗口内1最多。
right = 0：windowOnes += data[0] = 1，得1。right >= 3不成立，不减；right >= 2不成立，不更新。当前只是前缀[1]。
right = 1：windowOnes += data[1] = 0，仍是1。仍不减、不更新。前缀[1, 0]。
right = 2：windowOnes += data[2] = 1，得2。right >= 3不成立，不减。right >= 2成立，窗口首次成形为[0, 2] = [1, 0, 1]，含 2 个1，maxOnes = 2。
right = 3：windowOnes += data[3] = 0，仍是2；right >= 3成立，windowOnes -= data[0] = 1，得1。窗口是[1, 3] = [0, 1, 0]，确实只有 1 个1，与windowOnes一致。maxOnes保持2。
right = 4：windowOnes += data[4] = 1，得2；windowOnes -= data[1] = 0，仍是2。窗口是[2, 4] = [1, 0, 1]，含 2 个1，一致。maxOnes仍是2。循环结束，返回
3 - 2 = 1。验证一下：把下标0的1与下标3的0对调，数组变成[0, 0, 1, 1, 1]，三个1连成一段，确实一次交换就够。反过来看错误写法的后果：若把减法条件写成
right >= ones - 1，在right = 2时就会去取data[2 - 3] = data[-1]，Java 直接抛数组越界；若把返回值写成maxOnes，本例会输出2，比正确答案还大。
代码实现
class Solution {
public int minSwaps(int[] data) {
int ones = 0;
for (int num : data) {
if (num == 1) {
ones++;
}
}
if (ones <= 1) {
return 0;
}
int windowOnes = 0;
int maxOnes = 0;
for (int right = 0; right < data.length; right++) {
windowOnes += data[right];
if (right >= ones) {
windowOnes -= data[right - ones];
}
// 窗口长度固定为 ones，窗口里 1 越多，需要换入的 1 越少。
if (right >= ones - 1) {
maxOnes = Math.max(maxOnes, windowOnes);
}
}
return ones - maxOnes;
}
}
func minSwaps(data []int) int {
ones := 0
for _, num := range data {
if num == 1 {
ones++
}
}
if ones <= 1 {
return 0
}
windowOnes := 0
maxOnes := 0
for right := 0; right < len(data); right++ {
windowOnes += data[right]
if right >= ones {
windowOnes -= data[right-ones]
}
// 窗口长度固定为 ones，窗口里 1 越多，需要换入的 1 越少。
if right >= ones-1 && windowOnes > maxOnes {
maxOnes = windowOnes
}
}
return ones - maxOnes
}
复杂度分析
- 时间复杂度：$O(n)$。第一遍循环统计
ones是 $O(n)$；第二遍循环里每个下标只被「加入窗口」一次、「移出窗口」至多一次，循环体内全是常数操作，没有嵌套遍历。- 空间复杂度：$O(1)$。只用了
ones、windowOnes、maxOnes、right这几个标量，没有开前缀和数组或哈希表；这也是滑动窗口相对「先求前缀和再枚举区间」的优势。
关键点总结
- 目标窗口的长度不是要枚举的自由变量，而是由「交换不改变
1的总数」这个守恒量直接算出来的，识别出守恒量是这类题的第一步。- 「最少交换次数」被等价改写成「最大化窗口内
1的个数」，把最小化问题翻成最大化问题往往能让滑动窗口直接适用，这个转化值得在面试里明确讲出来。- 定长滑窗的模板是「先加右端、再按下标条件减左端、最后在窗口成形后统计」，三个动作的顺序和各自的边界条件互相咬合，改动其一必须同步检查其余两个。
- 元素只有
0和1时，sum += data[right]就等于计数，省掉分支；这类小技巧在面试里可以顺口提一句，但要说明前提是值域受限。- 面试时务必先确认数组是线性还是环形：本题是线性的，而 2134 题是同一个模型的环形版，处理方式是把数组复制一遍或用取模下标，答错这一点等于答错整题。
易错点总结
- 误以为要找「最长的连续
1段」然后用总数减去它：[1, 0, 1, 0, 1]里最长连续1段长度是1，会算出3 - 1 = 2，而正确答案是1；最优窗口未必是现成的连续段。- 返回
maxOnes而不是ones - maxOnes：[1, 0, 1, 0, 1]会输出2，把「已经就位的1」当成了「需要交换的次数」。- 减法条件写成
right >= ones - 1：ones = 3时right = 2就去访问data[-1]，Java 抛ArrayIndexOutOfBoundsException，Go 直接 panic。- 移出的下标写成
right - ones + 1：窗口实际长度缩成ones - 1。[1, 1, 0, 1, 1]（ones = 4）的最优窗口[1, 0, 1, 1]有 3 个1，缩短后的三长窗口最多只看到 2 个1，答案从1变成2。windowOnes += data[right]误写成windowOnes++：窗口里的0也被计入，[1, 0, 1, 0, 1]的每个满窗口都被当成有 3 个1，答案变成0。- 按环形数组处理首尾相接：
[1, 0, 0, 1]若允许跨越首尾，会认为两个1已经相邻而返回0，但本题数组是线性的，正确答案是1。- 试图模拟交换过程，把散落的
1逐个往中心挪：[1, 0, 1, 0, 1]这样数会得到 2 次，而实际只需 1 次；题目允许交换任意两个位置，代价与距离无关。- 漏掉
ones == 0的特判并在别的写法里踩坑：换成while (right - left + 1 > ones) left++这类变长写法时，窗口长度上限为0会让左指针越过右指针，产生负长度或死循环。maxOnes初值设成ones：[1, 0, 1, 0, 1]直接返回0，任何输入都会输出0，因为最大值永远不会被真实窗口刷新。- 统计
ones时误用数组长度或误统计0的个数：[0, 0, 1]会把窗口长度定为2，找的是错误尺寸的区间，答案随之偏离。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 643. 子数组最大平均数 I | 简单 | 定长窗口求和，长度由题目直接给出，无需先推导 |
| 1052. 爱生气的书店老板 | 中等 | 定长窗口最大化「额外收益」，窗口外的固定收益要单独累加 |
| 1456. 定长子串中元音的最大数目 | 中等 | 定长窗口计数，统计目标直接就是答案，不必再做减法转换 |
| 1423. 可获得的最大点数 | 中等 | 取两端等价于挖掉中间的定长窗口，需要先做一次问题反转 |
| 485. 最大连续 1 的个数 | 简单 | 不允许任何修改，只数现成的连续段，是本题的退化基线 |
| 487. 最大连续1的个数 II | 中等 | 允许翻转一个 0，窗口长度不再固定，改成变长窗口 |
| 1004. 最大连续1的个数 III | 中等 | 允许翻转 k 个 0，约束从「长度固定」变成「窗口内 0 数受限」 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 必须删掉一个元素，答案要在窗口长度上再减 1 |
| 424. 替换后的最长重复字符 | 中等 | 值域从二值扩展到 26 个字母，窗口内要维护最高频字符的出现次数 |
| 1156. 单字符重复子串的最大长度 | 中等 | 同样靠交换聚合，但只允许交换一次，且答案受该字符总数封顶 |