题目描述
思路解析动画文字版
记牢这一句:目标段长度就等于 1 的总数 k,用一个长度 k 的窗口在环形上滑一圈,窗口内 1 越多、要换进来的 0 就越少。下面从最左边的窗口开始滑。
第一步,把所有 1 找出来数个数。这组数据里绿色的 1 有三个,分别在位置 1、3、4,所以 k 等于 3。既然要把三个 1 聚拢,它们最后一定占据某段连续的三格。接下来的任务,就是找那段最省力的三格。
把一个长度 3 的窗口想成最终这段连续的 1 该落在哪。窗口里已经是 1 的可以留着不动,而窗口里的每一个 0,都得用一次交换,把外面的某个 1 换进来。所以这个窗口需要的交换次数,正好等于窗口里 0 的个数。现在这个开头窗口里有两个 0,代价是 2,并不划算,我们再往右滑看看。
算法先把窗口停在最左边,框住前 k 个也就是位置 0、1、2。数一数窗口里的 1,只有位置 1 那一个,cnt 记成 1。这是我们见到的第一个窗口,所以把历史最多 mx 也先记成 1。窗口里那两个 0,就是这一摆位要付出的交换数。
窗口整体向右挪一格。左边位置 0 的 0 滑出窗口,右边位置 3 的 1 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 1 的基础上加上进来的 1、减掉出去的 0,得到 2。这种进一个出一个的增量更新,是定长窗口省时间的关键。
结算这个窗口:里面绿色的 1 有 2 个,红色的 0 有 1 个,也就是摆在这里要交换 1 次。这个 cnt 比之前见过的都大,刷新历史最多 mx 到 2。窗口内 1 越多,要换的 0 就越少,这正是我们想要的方向。
窗口整体向右挪一格。左边位置 1 的 1 滑出窗口,右边位置 4 的 1 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 2 的基础上加上进来的 1、减掉出去的 1,得到 2。这种进一个出一个的增量更新,是定长窗口省时间的关键。
结算这个窗口:里面绿色的 1 有 2 个,红色的 0 有 1 个,也就是摆在这里要交换 1 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
窗口整体向右挪一格。左边位置 2 的 0 滑出窗口,右边位置 5 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 2 的基础上加上进来的 0、减掉出去的 0,得到 2。这种进一个出一个的增量更新,是定长窗口省时间的关键。
结算这个窗口:里面绿色的 1 有 2 个,红色的 0 有 1 个,也就是摆在这里要交换 1 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
窗口整体向右挪一格。左边位置 3 的 1 滑出窗口,右边位置 6 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 2 的基础上加上进来的 0、减掉出去的 1,得到 1。这种进一个出一个的增量更新,是定长窗口省时间的关键。
结算这个窗口:里面绿色的 1 有 1 个,红色的 0 有 2 个,也就是摆在这里要交换 2 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
窗口整体向右挪一格,这一步右端绕回了数组开头,正是环形的体现。左边位置 4 的 1 滑出窗口,右边位置 0 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 1 的基础上加上进来的 0、减掉出去的 1,得到 0。这种进一个出一个的增量更新,是定长窗口省时间的关键。
结算这个窗口:里面绿色的 1 有 0 个,红色的 0 有 3 个,也就是摆在这里要交换 3 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
窗口整体向右挪一格,这一步右端绕回了数组开头,正是环形的体现。左边位置 5 的 0 滑出窗口,右边位置 1 的 1 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 0 的基础上加上进来的 1、减掉出去的 0,得到 1。这种进一个出一个的增量更新,是定长窗口省时间的关键。
结算这个窗口:里面绿色的 1 有 1 个,红色的 0 有 2 个,也就是摆在这里要交换 2 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
窗口整体向右挪一格,这一步左端绕回数组开头,窗口正好回到最开始的位置 [0,2],和初始窗口重合。左边位置 6 的 0 滑出窗口,右边位置 2 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 1 的基础上加上进来的 0、减掉出去的 0,得到 1。这一格是多滑出来的,只是把第一个起点又走了一遍,结果不受影响。
结算这个窗口:里面绿色的 1 有 1 个,红色的 0 有 2 个,也就是摆在这里要交换 2 次。它没有超过当前的 mx 2,mx 保持不动,窗口已在环形上滑满一整圈,所有起点都覆盖到了,下面看最终答案。
窗口在环形上滑了一整圈,所有摆位都试过了。最好的窗口里有两个 1,mx 定格在 2。比如位置 1 到 3 这个窗口,里面位置 1 和位置 3 已经是 1,只有位置 2 是一个 0。要填满它,只需把这一个 0 换成 1,交换一次。这就是全场最省的方案。
来看这一次交换具体怎么发生。最优窗口位置 1 到 3 里,唯一的 0 在位置 2;窗口外面位置 4 有一个多出来的 1(紫色)。把这两个位置的值互换,位置 2 变成 1、位置 4 变成 0。交换过后数组是 [0,1,1,1,0,0,0],位置 1、2、3 三个 1 稳稳连在一起。一次交换搞定,和答案 1 完全对上。
回顾整个过程:先数出 1 的总数 k 等于 3,再用一个长度 3 的窗口在环形上滑一圈,记下窗口内最多的 1 是 mx 等于 2。最终答案就是 k 减 mx,3 减 2 等于 1。判定始终只看一件事:哪个长度 k 的窗口里现成的 1 最多,那里要换进来的 0 就最少。
边界想清:环形已相邻记 0、没有 1 记 0、全是 1 记 0,这几种都不需要交换。
面试重点:定长 k 窗口环形滑一圈求 1 的最大数,答案 k 减 mx,环形可取模或倍长数组。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minSwaps(self, nums: List[int]) -> int: k = nums.count(1) mx = cnt = sum(nums[:k]) n = len(nums) for i in range(k, n + k): cnt += nums[i % n] cnt -= nums[(i - k + n) % n] mx = max(mx, cnt) return k - mx复杂度
- 时间：O(n)，求 k 扫一遍数组是 O(n);之后下标从 k 走到 n 加 k,一共 n 步,每步只做加一个减一个再取最大的常数操作。整体随数组长度线性增长
- 空间：O(1)，只用 k、cnt、mx 这几个整数变量,不额外开数组;原数组不改动。空间是常数,与 n 无关
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问环形怎么处理,不想写取模有别的办法吗?
追问为什么是求 1 的最大个数而不是直接找 0 最少的窗口?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按符号重排数组
LeetCode 2149 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题