题目描述
思路解析
一句话答案：LeetCode 1536 排布二进制网格的最少交换：每次只能交换相邻两行，要让主对角线右上方全为 0。先数每行末尾连续的 0，再从上到下给每个位置就近挑一行够格的冒泡上来、累加移动距离，做不到返回 −1，时间 O(n²)。
网格要摆成什么样才算合格
给一个 n 行 n 列、只含 0 和 1 的网格，每次只能交换相邻两行，最少换几次能让主对角线右上方全为 0，做不到返回 −1。右上方指第 i 行第 i+1 列往右的格子，对角线和左边随便，也就是第 i 行末尾得有足够多连着的 0，位置越靠上需要的越多。
挨个试所有行排法为什么走不通
n 行有 n! 种先后顺序，全排开检查哪些合法、再挑交换最少的，n 才十几就爆了。而且每次只能换相邻两行，把一行挪到目标位得逐格挪，代价是移动距离。得找条不枚举全排列的路。
先数每行末尾的 0，就近挑一行上移
每行并不用摆到某个确定名次，只要末尾连续的 0 够盖住它所在位置的右上方就行。先量每行末尾连着几个 0，从右端往左数、碰到第一个 1 就停；位置 i 需要 n−1−i 个，谁够多谁往上放。
参考代码里换了个等价的量，记每行最右那个 1 在第几列、存进 pos 数组，末尾连续 0 就是 n−1 减去这列号，整行全 0 记 −1。位置 i 要末尾 0 够 n−1−i 个，换成列号看就是最右的 1 落在第 i 列或更左，两把尺子等价。之后就近取够格的行冒上来，总交换最省。
从上到下逐个位置安排够格的行
从位置 0 排到位置 n−1。轮到位置 i，从第 i 行起往下找第一个够格的行，记作第 j 行，把它一步步和上面相邻行对调、冒到第 i 位，一共 j−i 次交换累加进答案，被挤过的行整体下移一格。
冒上来的行就此锁定，就近取第一个不会亏：被换下的那些末尾 0 更多的行，落到更靠下、需求更松的位置照样够用。从第 i 行往下找不到够格的就返回 −1。
拿题面这张 3×3 网格从头排一遍
用题面的 grid=[[0,0,1],[1,1,0],[1,0,0]]，答案 3。数末尾 0：第 0 行 0、0、1 从右往左碰到第一个 1 就停、有 0 个；第 1 行 1、1、0 有 1 个；第 2 行 1、0、0 有 2 个。三行从上到下是 0、1、2。
位置 0 要不少于 2 个：前两行的 0 和 1 都不够，第 2 行的 2 个够格、离位置 0 有 2 步，累加 2、冒到顶，末尾 0 成 2、0、1。位置 1 要不少于 1 个：紧挨的行是 0 不够，下一行 1 够格、隔 1 步，累加 1，末尾 0 成 2、1、0。位置 2 只要 0 个、当前行本就 0 步。合计 2 加 1 加 0，答案 3。
末尾 0 只数右端连续段，别贪最多的行
求每行末尾 0 从右往左扫是 O(n²)；贪心阶段 n 个位置、每个往下找够格行和冒泡各最多 O(n) 次，也是 O(n²)。只额外开长度为 n 的数组记每行最右的 1，原地交换，空间 O(n)。
几个边界：单行网格没有右上方格子、天然合格，0 次；整张全 0 每行都管够，也 0 次；某位置往下凑不出够格行就返回 −1。最常写坏的：对角线那格不要求为 0，需求是 n−1−i 不是 n−i；末尾 0 只数右端连续那段，像 1、0、1、0、0 中间的 0 被 1 挡着不算、只有 2 个；也别去抢末尾 0 最多的行，挑最近刚够格的。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套打法:先数每行末尾连续 0 的个数,再从上到下给每个位置就近找一个够格的行冒泡上来,交换次数累加距离,中途找不到就是 -1。下面先把三行的末尾 0 都数出来。
初始网格 · 还没整理：这就是 3 行 3 列的网格。先看要求面板:位置 0 末尾要有 ≥ 2 个 0,位置 1 要 ≥ 1 个,位置 2 要 ≥ 0 个,也就是位置越靠上、末尾要的 0 越多。咱们先把每一行末尾连着几个 0 数出来。
哪些格子必须是 0：高亮的这几个格子就是主对角线右上方的区域,合格网格要它们全为 0。第 0 行有两个、第 1 行有一个、第 2 行一个都没有。一行末尾连着的 0 越多,就越能盖住右上方这片,所以越要往上放。
数第 0 行末尾连续的 0：看第 0 行 0、0、1,从右往左数,碰到第一个 1 就停。它末尾连着的 0 有 0 个。接着数下一行。
数第 1 行末尾连续的 0：看第 1 行 1、1、0,从右往左数,碰到第一个 1 就停。它末尾连着的 0 有 1 个。接着数下一行。
数第 2 行末尾连续的 0：看第 2 行 1、0、0,从右往左数,碰到第一个 1 就停。它末尾连着的 0 有 2 个。三行都数完了,末尾0 分别是 0、1、2。
末尾0 一览 · 0 / 1 / 2：三行末尾0 从上到下是 0、1、2,而位置 0、1、2 的需求是 2、1、0,正好反着来。现在从最上面的位置开始安排,需求最高的放最上面。
安排位置 0 · 需末尾0 ≥ 2：现在轮到位置 0,它需要末尾0 不少于 2 个。就从位置 0 自己开始往下看,找最近的、末尾0 够 2 的那一行。
看第 0 行 · 末尾0 = 0,不够：第 0 行末尾0 只有 0,不到 2,盖不住位置 0 右上方的格子,跳过它,继续往下看。
看第 1 行 · 末尾0 = 1,不够：第 1 行末尾0 只有 1,不到 2,盖不住位置 0 右上方的格子,跳过它,继续往下看。
看第 2 行 · 末尾0 = 2 ≥ 2：第 2 行末尾0 是 2,达到了 2,够格。它离位置 0 有 2 步,要用 2 次相邻交换把它一格一格冒泡上来。总交换次数先加上 2。
相邻交换 · 第 2 行与第 1 行对调：把它和上面那一行对调一次,它就往上挪了一格,现在到了第 1 行。还没到位置 0,再换一次。
相邻交换 · 第 1 行与第 0 行对调：把它和上面那一行对调一次,它就往上挪了一格,现在到了第 0 行。正好落到位置 0,这一轮的交换做完了。
位置 0 就位 · 末尾0 = 2 ≥ 2：位置 0 安排好了,这一行末尾0 是 2,满足 ≥ 2,右上方该为 0 的格子都盖住了。它就此锁定,后面的安排只在它下面进行。累计交换到现在是 2 次。
安排位置 1 · 需末尾0 ≥ 1：现在轮到位置 1,它需要末尾0 不少于 1 个。就从位置 1 自己开始往下看,找最近的、末尾0 够 1 的那一行。
看第 1 行 · 末尾0 = 0,不够：第 1 行末尾0 只有 0,不到 1,盖不住位置 1 右上方的格子,跳过它,继续往下看。
看第 2 行 · 末尾0 = 1 ≥ 1：第 2 行末尾0 是 1,达到了 1,够格。它离位置 1 有 1 步,要用 1 次相邻交换把它一格一格冒泡上来。总交换次数先加上 1。
相邻交换 · 第 2 行与第 1 行对调：把它和上面那一行对调一次,它就往上挪了一格,现在到了第 1 行。正好落到位置 1,这一轮的交换做完了。
位置 1 就位 · 末尾0 = 1 ≥ 1：位置 1 安排好了,这一行末尾0 是 1,满足 ≥ 1,右上方该为 0 的格子都盖住了。它就此锁定,后面的安排只在它下面进行。累计交换到现在是 3 次。
安排位置 2 · 需末尾0 ≥ 0：现在轮到位置 2,它需要末尾0 不少于 0 个。就从位置 2 自己开始往下看,找最近的、末尾0 够 0 的那一行。这次需求是 0,任何行都够格。
看第 2 行 · 末尾0 = 0 ≥ 0：第 2 行末尾0 是 0,达到了 0,够格。它离位置 2 有 0 步,本来就在位置上,不用交换。总交换次数先加上 0。
位置 2 就位 · 末尾0 = 0 ≥ 0：位置 2 安排好了,这一行末尾0 是 0,满足 ≥ 0,右上方该为 0 的格子都盖住了。它就此锁定,后面的安排只在它下面进行。累计交换到现在是 3 次。
全部就位 · 答案 3：三个位置都安排妥当,回看整张网格,主对角线右上方的格子全是 0,合格了。一路上做了 2 次再加 1 次相邻交换,一共 3 次,这就是最少交换次数,答案 3。
边界想清:单行网格天然合格、全 0 网格零次、四行相同且末尾 0 都不够时无解返回 -1。
面试重点:用交换论证证明就近贪心最优、求末尾 0 是 O(n²) 不是瓶颈、它和相邻交换排序同属「代价等于距离」一类。
参考代码
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, grid: List[List[int]]) -> int: n = len(grid) pos = [-1] * n for i in range(n): for j in range(n - 1, -1, -1): if grid[i][j] == 1: pos[i] = j break ans = 0 for i in range(n): k = -1 for j in range(i, n): if pos[j] <= i: ans += j - i k = j break if k == -1: return -1 while k > i: pos[k], pos[k - 1] = pos[k - 1], pos[k] k -= 1 return ans复杂度
- 时间：O(n²)，n 是网格边长。先求每行的 pos 要把每行从右往左扫,最坏是 O(n²);贪心阶段有 n 个位置,每个位置往下找够格行最多看 O(n) 行、冒泡又最多 O(n) 次相邻交换,合起来也是 O(n²)。整体由这两段平方主导,是 O(n²)
- 空间：O(n)，只额外开了一个长度为 n 的 pos 数组,记每行最右 1 的列号,按峰值就是 O(n)。没有按网格面积 n² 去开额外空间,交换是在原数组上原地进行
易错点
面试追问把动画讲成自己的话
追问为什么就近上移这个贪心一定最优,不会错过更省的方案?
追问把每行的末尾 0 个数求得更快有没有办法?
追问这道题和「把数组排成目标顺序的最少相邻交换次数」是不是一类?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
可以到达所有点的最少点数目
LeetCode 1557 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题