题目描述
思路解析
一句话答案：LeetCode 2134 最少交换次数来组合所有的 1 II 用环形定长滑动窗口：设 k 为 1 的总数，长度 k 的窗口在环上滑一圈找 1 最多的位置，答案是 k 减这个最多值。时间 O(n)、空间 O(1)。
环形数组上，这道题要凑出什么
给一个只含 0 和 1 的环形数组 nums，环形是说第一个和最后一个元素也算挨着。一次交换任选两个位置互换它们的值，问最少换几次能把所有的 1 挪到相邻的一段里。题面 nums=[0,1,0,1,1,0,0]，三个 1 分散在位置 1、3、4，只要一次交换换成 [0,1,1,1,0,0,0] 就全挨上了，答案是 1。
把 1 往哪段凑，为什么不能每种摆法都数一遍
所有 1 最终要占一段连续格子，那段落在哪、要挑。若把每个可能的落点都摆一遍、每摆一次就重新数这段里已经有几个 1、还缺几个得换进来，一段长度是 1 的个数、落点有 n 种，每种从头数一遍，就是 O(n²)，数组一长就吃力。
为什么那段的长度，铁定等于 1 的总数
先把 1 的总数记成 k。不管最后 1 聚在哪，聚拢后正好是 k 个 1 挨成一排，占据的就是长度恰为 k 的一段——多一格少一格都装不下正好 k 个 1。于是落点虽多，每个都对应一个长度 k 的窗口。窗口里本来就是 1 的留着不动，每一个 0 都得花一次交换、把窗外的某个 1 换进来。所以这个窗口要的交换次数，正好等于窗口里 0 的个数。窗口里 1 越多，0 越少，越省。要找的就是 1 最多的那个窗口，答案 = k 减窗口内最多的 1。
窗口怎么在环上滑一圈，又不用每步重数
把长度 k 的窗口先停在最左，框住前 k 格，数出里面有几个 1 记作 cnt，也把见过的最大值 mx 记成它。之后窗口每次整体右移一格：右端进来一格就把它的值加到 cnt，左端出去一格就把它的值从 cnt 减掉，一进一出只做两次常数操作，不必重数。下标一旦超过末尾就取模绕回开头，这样横跨首尾的窗口也覆盖得到——最优的一段 1 可能正跨在数组末尾和开头之间。滑满一圈、每个起点都试过，mx 就是全局最多的 1。
顺着 [0,1,0,1,1,0,0] 把每个窗口的账结一遍
先数出 3 个 1，起手窗口 [0,1,2] 是 0、1、0，cnt=1，mx=1。右移到 [1,2,3]，进位置 3 的 1、出位置 0 的 0，cnt=2，mx 刷到 2。再到 [2,3,4]，进 1 出 1，cnt=2。[3,4,5] 进 0 出 0，cnt=2。[4,5,6] 进 0、出位置 3 的 1，cnt=1。[5,6,0] 右端取模绕回开头，进 0 出 1，cnt=0。[6,0,1] 进 1 出 0，cnt=1。[0,1,2] 回到起点，cnt=1。滑满一圈 mx=2，答案 k 减 mx = 3 减 2 = 1。
窗口长度取错、忘了绕圈，答案会往哪偏
数一遍 1 是 O(n)，滑一圈 n 步每步常数，整体 O(n)；只用 k、cnt、mx 几个整数变量，空间 O(1)。几处一写就偏：窗口长度必须恰好是 k，随手换个别的值，对应的就不是一个装得下 k 个 1 的合法目标段。只在直线上滑、不给下标取模，横跨末尾和开头的那些窗口会被漏掉，mx 偏小、答案偏大。还有把答案当成窗口里最多的 1，方向反了——要的是换掉的 0 的个数，是 k 减 mx，不是 mx。环形已相邻、没有 1、全是 1 这几种都不用换，答案是 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:目标段长度就等于 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题