LeetCode 1536 这道题，我第一次在周赛里碰到的时候，大概花了十五分钟才把那个看着很唬人的二维网格条件翻译成人话。题目长得挺吓人：给你一个 n×n 的二进制矩阵，每次可以交换相邻两行，目标是让主对角线右上方的所有格子都变成 0，问最少交换多少次。如果你第一次看，极容易被 n×n 的矩阵结构带偏，满脑子都是各种坐标变换；但真正动手之后会发现，绝大多数格子都是干扰信息，每一行有意义的只有“最后一个 1 落在哪一列”这一件事。这篇文章就把这道题的建模、贪心思路、代码实现和踩坑点完整过一遍，适合正在刷数组、贪心和模拟类题目的同学参考。

这道题在很多面试场景里属于“看着难、点破了就很简单”的类型，刷 LeetCode 热门 100 题或者准备周赛的时候，值得把它当成一个“从二维结构抽象成一维约束”的经典案例来练手。下面我直接开讲。

1. 把网格约束压缩成一个数组

1.1 条件到底是什么意思

先明确目标：对排布完成后的矩阵，主对角线右上方，也就是所有满足“列号 > 行号”的格子，都必须为 0。

拿 n = 3 举例，假设排布后的矩阵长这样：

行0: □ □ ■ 行1: □ ■ □ 行2: ■ □ □

主对角线是 (0,0)、(1,1)、(2,2) 这三个格子。右上方区域是：

• 第 0 行的第 1 列、第 2 列；
• 第 1 行的第 2 列；
• 第 2 行没有右上方格子。

换句话说，排布完成后，第 i 行的所有“列号大于 i”的格子必须是 0。这里要注意：对角线本身和左下区域没有任何限制，它们可以是 0 也可以是 1。

很多新手会在这里搞反，以为是“第 i 行的前 i 列必须为 0”，那其实是左下三角的条件，不是本题的条件。一旦方向搞错，后面整个算法都是错的。如果你拿不准，就在草稿纸上画一个 3×3 的方格，把主对角线画出来，再标出右上方区域，一眼就能看清。

1.2 核心建模：只用关心“最后一个 1”

既然第 i 行要求“列号 > i 的位置全为 0”，那这一行的前 i 列和主对角线位置即使有 1 也无所谓。于是对每一行来说，真正起决定作用的，就是这一行里最右边的那个 1 出现在哪一列。

我用 last[i] 表示第 i 行最右侧 1 的列号。如果这一行全是 0，可以认为 last[i] = -1，方便统一处理。

为什么只看这个位置？因为如果一行的最后一个 1 在列 p，那么：

• 把这一行放在第 i 行时，所有列号大于 i 的格子必须为 0；
• 如果 p > i，说明在右上方区域里出现了一个 1，这一行放在第 i 行就是非法的；
• 如果 p <= i，说明即使有 1，也都在主对角线或左下区域，这一行放在第 i 行就是合法的。

所以每一行能放的位置，是一个“后缀区间”：从 last[i] 开始，一直到 n-1 都可以放。全 0 行的 last[i] = -1，相当于从第 0 行开始哪里都能放。

用一个表格可以看得很清楚，假设 n = 3：

到这里，题目就从“操纵一个二维矩阵”压缩成了“操纵一个长度为 n 的数组 last”。后面所有交换操作，只需要围绕这个数组进行，根本不需要关心原始矩阵里的其他格子。

1.3 把问题看成“排队入座”

换个视角：现在有 n 行，每行手里拿着一张票，票上写着一个数字 last[i]，表示“我必须被安排在座位号 >= last[i] 的位置上”。你要通过交换相邻两行的方式，把所有人排好队，使得坐在第 i 个座位上的人，其票面数字满足 last <= i。

这就像一群乘客按登机牌排队，有人要求“我必须坐在 2 号座或更靠后”，有人无所谓。我们要用最少的相邻交换，让每个人都满意。

这个抽象非常关键，因为一旦变成“每个人有一个最低可坐座位号”，我们就能用贪心去处理，而不是去枚举所有排列。

2. 贪心策略：先满足最严格的位置

2.1 为什么从第 0 行开始处理

一个很容易想到的切入点：位置 0 的要求最严格，因为第 0 行要求整个右侧部分全部为 0，即 last <= 0；位置 1 的要求稍微宽松一点，要求 last <= 1；越靠后的位置越宽松。

这启发我们按位置从前往后逐个处理。每处理一个位置 i，就在“还没被固定的行”里找一个满足 last <= i 的行，把它通过相邻交换挪到第 i 个位置来。

这样做的好处是：前面的位置一旦被固定，后面不管怎么交换，都不能再碰它，否则前面好不容易满足的条件又会被破坏。从前往后处理，刚好符合这种“先锁死最严格约束”的直觉。

2.2 算法主流程

假设我们已经预处理出数组 last，长度是 n。

主循环如下：

• 令当前位置 i 从 0 开始，直到 n-1；
• 从下标 i 开始往后扫描，找到第一个满足 last[k] <= i 的行 k；
• 如果找不到，直接返回 -1，因为没有任何一行能满足当前位置的约束，整体无解；
• 如果找到了，就把第 k 行通过连续相邻交换，一步一步挪到位置 i。每跨越一个行，操作次数加 1；
• 继续处理 i+1。

为什么是“第一个”满足条件的行，而不是最后一个？因为对于当前这一步来说，挪得越近，花费的交换次数越少。第 i 个位置只要求某个行的 last <= i，具体选哪一行并不影响“当前位置是否合法”这个结果，所以从最近的地方找一个合适的行过来，是最划算的。

2.3 正确性直觉与证明

这种贪心不是拍脑袋，它有一个很清晰的归纳证明思路。

在每一步开始时，前 i 行已经固定并且全部合法，它们以后不会再移动。对于位置 i，需要从剩余行中选一个满足 last <= i 的行。这个选择是必须的，因为位置 i 的约束无法绕过。

如果把满足条件的行都列出来，设为 k1 < k2 < ... < km，那么任选其中一个 kj，把它挪到位置 i，需要 kj - i 次相邻交换。显然选择最小的 k1 时，当前这一步的代价最小。

剩下要证明的是：选择 k1 不会让后续步骤变得更糟。这一点可以这样看：选择哪个满足条件的行，只会改变“谁被放到位置 i”以及“其他剩余行的相对顺序”。但剩余行的集合始终是同一批，只是它们在数组中的顺序不同。而后续每个位置需要满足的条件只和 last 值有关，和具体是“哪一行”无关。因此，既然存在一种方案从任意一个满足条件的行出发能完成后续任务，那么从最近的 k1 出发也一定能完成，并且当前这一步代价最小。由归纳法，整体就是最优的。

这在形式上很像选择排序：每一轮选一个满足条件的元素，把它“浮”到当前处理位置。相邻交换的累计次数，就是题目要求的最少操作次数。

2.4 一个完整的手算示例

用 LeetCode 官方的测试用例来走一遍：n = 3，grid = [[0,0,1], [1,1,0], [1,0,0]]。

先算每行的 last：

• 第 0 行 [0,0,1]，最右侧 1 在列 2，last[0] = 2；
• 第 1 行 [1,1,0]，最右侧 1 在列 1，last[1] = 1；
• 第 2 行 [1,0,0]，最右侧 1 在列 0，last[2] = 0。

所以 last = [2,1,0]。

处理位置 0：

• 扫描 k = 0，last[0] = 2 > 0，不行；
• k = 1，last[1] = 1 > 0，不行；
• k = 2，last[2] = 0 <= 0，找到了；
• 把行 2 从位置 2 挪到位置 0，需要 2 次相邻交换；
• 交换后 last 变成 [0,2,1]，同时实际网格里的行也对应变成 [原第2行, 原第0行, 原第1行]。

处理位置 1：

• 现在 last = [0,2,1]；
• k = 1，last[1] = 2 > 1，不行；
• k = 2，last[2] = 1 <= 1，找到了；
• 把行 2 从位置 2 挪到位置 1，需要 1 次相邻交换；
• 交换后 last = [0,1,2]。

此时所有位置都满足条件，总交换次数为 2 + 1 = 3。

这就是官方的输出 3。整个过程里，我们其实只关心 last 数组的变换，最终 last 变成非递减的 [0,1,2]，说明每一行都找到了自己能接受的位置。

3. 代码实现与细节

3.1 预处理阶段

核心代码很简单，但预处理是很多人的第一个坑。计算 last 时，从右往左扫描每一行，碰到第一个 1 就停下来，这样最省时间。

def minSwaps(grid): n = len(grid) last = [-1] * n for i in range(n): for j in range(n - 1, -1, -1): if grid[i][j] == 1: last[i] = j break ...

如果这一行全是 0，last[i] 保持 -1，代表它可以放到任意位置。这个 -1 在后面的比较中非常方便，因为 -1 <= i 对任何 i 都成立。

3.2 主循环：最简单的 Python 版本

一种非常简洁的写法是只维护 last 数组，不真正去交换 grid，因为题目只要求返回操作次数，不要求输出排布后的矩阵。

def minSwaps(grid): n = len(grid) last = [-1] * n for i in range(n): for j in range(n - 1, -1, -1): if grid[i][j] == 1: last[i] = j break ans = 0 for i in range(n): # 找到第一个满足 last[k] <= i 的行 k = i while k < n and last[k] > i: k += 1 # 找不到就直接无解 if k == n: return -1 # 把第 k 行“上浮”到第 i 行，每跨一步记一次交换 while k > i: last[k], last[k - 1] = last[k - 1], last[k] ans += 1 k -= 1 return ans

这段代码最妙的地方在于，交换 last 数组的同时，其实就相当于在交换对应的行；而因为我们后续判断只依赖 last，所以根本不用去动二维矩阵。如果哪天面试官追问“如果我要输出最终矩阵怎么办”，那你就在交换 last 的同时，同步交换 grid 的两行即可。

3.3 同步交换 grid 的版本

如果你希望代码和题目中的矩阵保持一一对应，可以在主循环里加上同步交换网格的操作：

def minSwaps(grid): n = len(grid) last = [-1] * n for i in range(n): for j in range(n - 1, -1, -1): if grid[i][j] == 1: last[i] = j break ans = 0 for i in range(n): k = i while k < n and last[k] > i: k += 1 if k == n: return -1 while k > i: grid[k], grid[k - 1] = grid[k - 1], grid[k] last[k], last[k - 1] = last[k - 1], last[k] ans += 1 k -= 1 return ans

两行、两个数组同时交换，保证状态始终一致。这种写法在调试的时候更方便，因为你可以随时打印 grid 来人工验证排布结果是否合法。

3.4 C++ 版本要点

用 C++ 写的时候思路一样，只是要注意用引用或者直接 vector 传参。核心循环保持 O(n^2) 的复杂度完全没问题，因为题目的 n 通常只有 200 左右。

class Solution { public: int minSwaps(vector<vector<int>>& grid) { int n = grid.size(); vector<int> last(n, -1); for (int i = 0; i < n; i++) { for (int j = n - 1; j >= 0; j--) { if (grid[i][j] == 1) { last[i] = j; break; } } } int ans = 0; for (int i = 0; i < n; i++) { int k = i; while (k < n && last[k] > i) k++; if (k == n) return -1; while (k > i) { swap(grid[k], grid[k - 1]); swap(last[k], last[k - 1]); ans++; k--; } } return ans; } };

用swap函数交换两行时，需要grid的类型本身支持赋值，vector<vector<int>>是支持的，这一点不用担心。

3.5 复杂度分析

预处理阶段，每一行最多扫描 n 列，所以是 O(n^2)。

主循环阶段，外层 i 循环 n 次，每次找一个满足条件的行最多扫 n 个位置；“上浮”操作每处理一个位置，最多把某一行从最后面挪到最前面，累计交换次数最多是 O(n^2) 量级。因此总复杂度是 O(n^2)。

空间上只需要一个长度为 n 的 last 数组，是 O(n) 额外空间。这个复杂度对 n <= 200 的数据范围来说绰绰有余，很多比赛里甚至可以用更暴力的写法也能过。

4. 那些容易翻车的细节

4.1 常见错误清单

我在实际写这道题的时候，第一版代码就挂在了一个看起来很不起眼的边界上。这里整理一份“踩坑速查表”。

这里面最经典的，就是把“最右侧 1 的列号”理解成“从右往左数第一个 1 前有多少个 0”。其实这是两种等价描述，但如果你不统一好，很容易在判断条件时写反。建议始终使用“最右侧 1 的列号 col”，然后判断col <= i。

4.2 调试技巧：先写一个 checker

如果你在做这道题时卡住了，最有效的排查方式不是盯着输出结果冥思苦想，而是写一个验证函数，检查某个排布后的矩阵是否满足“对角线右上方全为 0”。

def check(grid): n = len(grid) for i in range(n): for j in range(i + 1, n): if grid[i][j] != 0: return False return True

然后在你的交换过程中，每一步之后调用这个 checker，看看到底是从哪一步开始变得不合法的。这个办法能帮你快速定位是取值错误，还是交换逻辑错误。

另外，我建议遇到这种“交换数组元素”的题，先用小规模数据手动模拟一遍，比如 n = 3、n = 4，把每次交换后的数组状态写下来，再对照代码输出。绝大多数 bug 都能被这种方式找出来。

4.3 无解判断的直观理解

什么时候会无解？假设处理到位置 i 时，剩下的所有行里没有一个人满足 last <= i，说明当前这行无论怎么排都没法满足条件，自然整个任务就无解了。

一个更全局的判断方法是：如果某个位置 i 之前，所有行的 last 都大于 i，那直接返回 -1。用代码实现时就是在主循环的while扫描结束后判断k == n。

很多初学者会忘记这个分支，最后得到一堆莫名其妙的交换次数。这一点必须铭记：不是所有输入都有解，有些矩阵天生就不可能排成满足条件的形态。

5. 变体与延展思考

5.1 如果题目改成交换列怎么办

很多题目会故意换个壳，比如把“交换相邻两行”改成“交换相邻两列”，或者把目标从“右上方全 0”改成“左下方全 0”。

这时候不要慌，观察一下条件。如果是交换列，你可以把整个 grid 转置一下，转置之后“右上方全 0”依然是某种三角区域全 0 的问题，然后再用同样的贪心处理。矩阵转置这个操作在代码里只需要两层循环交换下标即可。

如果是要求“对角线左下方全 0”，你可以把每行反转，也就是把列顺序反过来，右上方和左下容易互相转换。掌握“转置 + 反转”这两个工具，很多变体题都能秒变原题。

5.2 只维护 last 数组的面试解释

面试时，如果你只写了维护 last 数组的版本，面试官可能会问你“为什么不用交换二维矩阵？”

你可以这样回答：因为决定一行能否放在某个位置的，只有它的 last 值。交换两行这个行为，反映在 last 数组上就是两个元素交换位置。所有后续判断都不需要知道每行内部的 1 具体分布在哪些列，因此二维矩阵中的所有其他信息都是冗余的。保留 last 数组已经足够还原所有关键状态，能够正确计算出最小交换次数。

这个回答本身也是一个加分项，因为它展示了你对问题本质的理解，而不是只会照着模板敲代码。

5.3 与最小相邻交换排序的联系

这道题其实可以归入一个更通用的模型：给定一个序列，每个元素有一个限制值，要求通过相邻交换，把它排成满足某种偏序关系的形态，求最少交换次数。

这个模型和经典的“用相邻交换把序列排序”非常像。区别在于，排序要求的是完全有序，而本题只要求每个位置上的元素满足一个单边限制 last <= i。正因为限制比较弱，我们只需要用贪心逐位处理，不需要做真正意义上的排序。

如果 n 特别大，想要优化到 O(n log n)，可以尝试用树状数组或者平衡树维护剩余元素的 last 最小值，再配合统计逆序对的思想。不过 LeetCode 原题的数据范围很小，O(n^2) 已经是最稳妥、最好理解的做法，不建议为了炫技引入复杂的常数优化。

最后再分享一个实战中的小技巧：做这种“网格排布”类题目，第一步永远是找冗余信息。一个 n×n 矩阵里有 n^2 个数，但真正影响答案的往往只有一个很小的维度。LeetCode 1536 就是把 n^2 压缩成 n 的典型例子。以后你再遇到类似题目，先问自己一句：“决定答案的，到底有哪些变量？”然后优先把变量量级降下来，再设计算法，思路会清晰很多。