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行内容最右侧 1 的列号可以放的行号[0,0,1]22[0,1,0]11, 2[1,0,0]00, 1, 2[0,0,0]-10, 1, 2到这里题目就从“操纵一个二维矩阵”压缩成了“操纵一个长度为 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继续处理 i1。为什么是“第一个”满足条件的行而不是最后一个因为对于当前这一步来说挪得越近花费的交换次数越少。第 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 3grid [[0,0,1], [1,1,0], [1,0,0]]。先算每行的 last第 0 行 [0,0,1]最右侧 1 在列 2last[0] 2第 1 行 [1,1,0]最右侧 1 在列 1last[1] 1第 2 行 [1,0,0]最右侧 1 在列 0last[2] 0。所以 last [2,1,0]。处理位置 0扫描 k 0last[0] 2 0不行k 1last[1] 1 0不行k 2last[2] 0 0找到了把行 2 从位置 2 挪到位置 0需要 2 次相邻交换交换后 last 变成 [0,2,1]同时实际网格里的行也对应变成 [原第2行, 原第0行, 原第1行]。处理位置 1现在 last [0,2,1]k 1last[1] 2 1不行k 2last[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 ...如果这一行全是 0last[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(vectorvectorint grid) { int n grid.size(); vectorint 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的类型本身支持赋值vectorvectorint是支持的这一点不用担心。3.5 复杂度分析预处理阶段每一行最多扫描 n 列所以是 O(n^2)。主循环阶段外层 i 循环 n 次每次找一个满足条件的行最多扫 n 个位置“上浮”操作每处理一个位置最多把某一行从最后面挪到最前面累计交换次数最多是 O(n^2) 量级。因此总复杂度是 O(n^2)。空间上只需要一个长度为 n 的 last 数组是 O(n) 额外空间。这个复杂度对 n 200 的数据范围来说绰绰有余很多比赛里甚至可以用更暴力的写法也能过。4. 那些容易翻车的细节4.1 常见错误清单我在实际写这道题的时候第一版代码就挂在了一个看起来很不起眼的边界上。这里整理一份“踩坑速查表”。错误类型错误写法后果把 last 记成“前导 0 的个数”例如把 [0,0,1] 记成 2条件方向完全反掉后面判断全乱从 0 开始找满足条件的行for k in range(0, n)可能把已经固定好的行再交换破坏前面结果找不到行时返回 0return 0明明是 -1 的情况却返回 0交换时只交换 grid 没交换 last矩阵对了 last 不对后续判断基于错误状态答案错“上浮”方向写反for k in range(i, target)反向交换次数多算或者少算把 last 初始值设成 n 而不是 -1全 0 行无法放到任意位置无解误判这里面最经典的就是把“最右侧 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 的典型例子。以后你再遇到类似题目先问自己一句“决定答案的到底有哪些变量”然后优先把变量量级降下来再设计算法思路会清晰很多。