题目描述
思路解析动画文字版
记住这套打法:先数每行末尾连续 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题