1. 题目理解与核心思路先想清楚“交换”到底在交换什么LeetCode 1536 这道题光看名字“排布二进制网格的最少交换次数”可能会劝退一波人。二进制网格、交换次数、最少次数,三个关键词一叠加很多人第一反应就是“这是不是又要模拟矩阵旋转或者行列互换”。实际上刷完这道题你会发现它表面上是二维网格骨子里是一维数组的贪心排序问题甚至连排序都不需要只需要做“按需选择”和“计数交换”。先看题目本身。给定一个 n x n 的二进制矩阵 grid里面的元素只有 0 和 1。允许的操作是任意选择相邻的两行第 i 行和第 i1 行进行交换且这个操作可以重复执行。目标是让主对角线以下的元素全部为 0也就是满足第 0 行的所有列列 0 到列 n-1都必须是 0第 1 行的列 1 到列 n-1 都必须是 0第 2 行的列 2 到列 n-1 都必须是 0第 i 行的列 i 到列 n-1 都必须是 0。换句话说每一行 i 从左侧开始数至少要“足够多”的连续 0覆盖掉从列 0 到列 i 之前的位置。这里有个关键点只要求对角线以下为 0对角线及对角线右边的位置是什么都无所谓1 留在那里不影响我们通过题目判定条件。那“相邻行交换”这个操作对应到实际问题里是什么用一个生活化类比假设每行是一张写满 0 和 1 的卡片卡片不能拆开只能整体交换位置。每一张卡片有一个属性——它末尾或者更准确地说从右侧开始向左边数有多少个连续的 0。这里要特别注意不是看整个行里有多少个 0而是看从右往左0 最多能连续到哪一列。这个属性其实就是“该行最多能合法放在第几个位置”的通行证。举个例子某一行是 [1, 0, 0, 1, 0]n5。从右往左看最后一个元素是 0倒数第二个是 1所以连续 0 的个数是 1。这意味着这行只能作为“从列 4 开始都可以是 0”的行也就是它可以放在第 4 行因为第 4 行只需要保证列 4 及其右边为 0。它不能放到第 3 行因为第 3 行要求列 3、列 4 都为 0而这行在列 3 是 1。所以核心问题被抽象成了一个一维模型每一行有一个“后缀连续 0 长度”属性记为 pos[i]。目标是把这些行重新排列使得排列后第 i 行的 pos 值 ≥ (n - 1 - i)。注意这里的编号关系第 0 行要求后缀 0 长度至少为 n也就是整行全 0第 1 行要求至少为 n-1以此类推第 n-1 行至少为 1。也可以换一种常见写法第 i 行要求 pos[i] ≥ n - 1 - i因为从列 i 到列 n-1 恰好是 n-i 个位置。把所有行都抽象成一排带有“能力值”的对象问题就变成了通过交换相邻对象让最终序列中第 i 个对象的“能力值”不低于某个阈值 target[i]。由于只能交换相邻两行交换一次计数加一。目标是最小化总交换次数。这一步想通之后后面要做的就非常机械了。真正考验人的点其实在“为什么每次把能放在当前位置的行拿上来就是最优”以及“怎么用代码优雅地实现而不是真的去模拟矩阵交换”。这道题适合的读者不只是准备算法面试的人。如果你在写各类调度问题、任务排期、甚至是在做数据清洗时需要对二维数组按某种“行特性”重排这个思路都能迁移过去。刷 LeetCode 题解久了你会发现很多困难题其实都是“定义好状态之后从一个你没想过的地方开始贪心”。2. 贪心策略的正确性证明为什么每次选当前位置能放的行就一定全局最优这道题的标准解法是贪心但很多人刷题时有个坏习惯一看到能贪心就写写完了样例过了就觉得自己懂了根本不追问贪心为什么成立。LeetCode 的测试数据越来越刁钻这类问题如果不理解正确性换个包装可能就翻车。这里我把贪心策略掰开来讲。先明确目标序列的约束。我们最终要满足第 0 行的后缀 0 长度至少为 n第 1 行至少 n-1...第 n-1 行至少 1。也就是说越靠前的行要求越严格越靠后的行要求越宽松。如果把所有行的“后缀零长度”降序排列那么天然满足要求。问题在于原数组不一定有序要通过相邻交换达到一个可行排列。标准做法是从第 0 行开始在第 0 行到第 n-1 行之间找到第一个满足 pos[j] ≥ n 的行 j把它一路向上交换到第 0 行每交换一次记一次数。然后固定在当前位置继续对第 1 行做同样的事情找到第一个满足 pos[j] ≥ n-1 的行交换到第 1 位。依此类推。如果某一步找不到符合条件的行直接返回 -1。为什么这种“每次取最靠前的可用行”的策略一定是最优的关键在于两点。第一如果一个行已经满足当前行的位置要求那么它的“能力”是有冗余的。比如当前处理到第 i 行需要 pos ≥ n-1-i而某行的 pos 远大于这个值那么它放到更靠前的位置也一样合法。这说明我们不需要对“候选行的顺序”做进一步局部调整任何能放在当前行的候选行都可以被“消耗”在这里不会影响后续行数。第二我们选择“当前最靠前的候选行”而不是“当前能力最大的候选行”为什么不会更差这里有一个比较经典的交换论证思路。假设当前处理到第 i 行我们通过若干相邻交换把某个合法行 j 放到了第 i 行。如果我们不选择 j而是选择另一个更靠后的合法行 k那么 j 仍然留在位置 i 与 k 之间。后续我们依然需要把 j 交换到某个靠前的位置吗不一定因为 j 可能被安排在更靠后的位置。但问题在于如果把 k 交换上来的次数是 dist(i, k)把 j 交换上来的次数是 dist(i, j)由于 j 排在 k 前面dist(i, j) dist(i, k)。选择 j 的交换次数更少而 k 的能力不低于 j 吗注意这里不一定但 k 是合法行说明 k 的能力也大于等于当前阈值而 j 的位置在 k 之前所以 j 被留下后需要被移到别处。由于 j 在前面把它往后移或者留到后面和 k 相比不会增加额外开销。更严谨的证明思路是这样贪心选择第 i 位置上的一个合法行等价于“在所有合法行中选下标最小、让它移动距离最短的”。若存在其他最优解中第 i 行放的是一个下标更大的合法行我们把该解的序列中第 i 行那个元素与当前下标更小的合法行交换位置会发现更小的下标行有更大的 pos 吗不一定但至少数量级上如果它更靠前且仍是合法行把它换到 i 后原第 i 行的那个元素挪到它原本的位置由于原始序列中它的下标小于另一个元素这次交换涉及的相邻交换次数不会大于原方案的总次数。通过这样的调整可以把任意最优解逐步变为贪心解而不增加代价所以贪心是最优的。这里还可以从另一个角度帮助理解整个过程等价于“把需要前移的行移到目标位”每移动一个跨过多少行人就消耗多少步。因为只允许相邻交换移动一个元素跨过 x 个元素需要 x 次。贪心每一步都选“当前需要移动距离最短的合法行”这就避免了把较远行拉过来造成无谓开销。我用一个简单的例子说明。假设某一行 pos 值分别是 [3, 1, 2, 4]n4目标阈值依次为 [4, 3, 2, 1]。处理第 0 行找第一个 pos ≥ 4 的行是下标 3pos4。把它从第 3 位交换到第 0 位需要 3 次相邻交换。此时顺序变成 [4, 3, 1, 2]。处理第 1 行在剩余行中找 pos ≥ 3 的行只剩 pos3 的那行它恰好已经在第 1 位交换次数 0。处理第 2 行找 pos ≥ 2 的行pos2 在下标 3把它交换上来需要 1 次。最终顺序 [4, 3, 2, 1]总次数 4。如果第 1 步不去交换 pos4 的行而是试图先把 pos3 的行放上来会发现它根本不满足第 0 行要求所以无可选。贪心策略在每一步其实把所有非法项直接排除了强制的意味更多。3. 代码实现与细节拆解从预处理到交换计数的完整落地思路清楚了代码写起来其实很短。难点在于怎么把“后缀连续 0 长度”算得干净利落以及怎么做到 O(n^2) 的复杂度而不是 O(n^3) 的模拟。3.1 第一步计算每行的后缀零数量这一步有两个常见姿势。第一种是老老实实从每一行的末尾往前遍历遇到 1 就停。第二种是每一行从右往左数 0用一个变量统计。我建议用第一种逻辑最直观int n grid.length; int[] pos new int[n]; for (int i 0; i n; i) { int count 0; // 从右往左数 0 for (int j n - 1; j 0 grid[i][j] 0; j--) { count; } pos[i] count; }这里有个细节为什么 count 是从右往左连续 0 的个数而不是整行 0 的总数因为题目条件要求的是“从列 i 到列 n-1 全为 0”也就是只要从某一列开始到末尾全是 0 就行中间不能有间断。如果整行是 [1, 0, 0, 0, 1, 0]末尾连续 0 是 1尽管整行有很多 0但它在倒数第二列有一个 1导致它只能被放到最后一行的位置。这是很多人第一步就容易踩坑的地方会把“0 的总数”和“后缀连续 0 个数”搞混。3.2 第二步贪心交换与计数预处理出 pos 数组之后就完全不碰 grid 了。后面所有的交换都是在“行下标”上做文章。这里有一个业界很常见的优化不要真的去交换 pos 数组里的元素而是用一个“虚拟重排”的方式跳过已固定行。标准做法具象化是这样的int ans 0; for (int i 0; i n; i) { // 目标要求第 i 行需要 pos n - 1 - i int need n - 1 - i; // 在 i 到 n-1 之间找第一个满足条件的行 int j i; while (j n pos[j] need) { j; } if (j n) { return -1; // 没有行能满足当前行要求 } // 把 j 行往上升到 i 行中间跨过的每一行都要交换一次 for (int k j; k i; k--) { int tmp pos[k]; pos[k] pos[k - 1]; pos[k - 1] tmp; ans; } } return ans;这个循环的时间复杂度是多少外层 for 循环是 n 次while 查找最坏情况是 n 次内层交换循环也是 n 次所以整体是 O(n^2)。对于 n ≤ 50 的约束本题 n 的范围一般不大这个复杂度完全够用。如果 n 到 1000 或者更大也可以用 BIT 树状数组或者 Fenwick 树来维护“剩余行在原始数组中的下标”但 LeetCode 原题根本不需要O(n^2) 是最优雅的。注意一个比较容易写错的地方内层交换循环里无论 pos[j] 是否满足条件我们都是从 j 一路往前 “ bubble ” 到 i。这一路交换的计数就是 j - i而不是每交换一对就看一下 pos 值是否合法。因为目标只是计数中间过程无需真正验证合法性。其实这也是“最小相邻交换次数”的通用计数方法把一个元素从位置 j 移动到位置 i最少需要 j-i 次相邻交换。这里不需要真的交换一两下就停下来评估直接算差值即可。如果你把这个循环优化成ans j - i;然后手动把 pos 数组里的元素重新排列效果一样但代码更简洁int val pos[j]; // 从 j-1 到 i 的位置全部后移一位 System.arraycopy(pos, i, pos, i 1, j - i); pos[i] val; ans j - i;这样省去了逐对交换的循环还能降低常数。不过话说回来对这道题的规模怎么写都无所谓主要是思路要清晰。3.3 一个完整可运行的 Java 示例我把完整类结构写出来方便你直接复制去 LeetCode 上提交class Solution { public int minSwaps(int[][] grid) { int n grid.length; int[] pos new int[n]; // 计算每行从右到左连续 0 的个数 for (int i 0; i n; i) { int cnt 0; for (int j n - 1; j 0; j--) { if (grid[i][j] 0) { cnt; } else { break; } } pos[i] cnt; } int ans 0; for (int i 0; i n; i) { int need n - 1 - i; int j i; while (j n pos[j] need) { j; } if (j n) { return -1; } // 把 pos[j] 移到位置 i并累计交换次数 ans j - i; int val pos[j]; for (int k j; k i; k--) { pos[k] pos[k - 1]; } pos[i] val; } return ans; } }这段代码的边界条件已经自然覆盖了这几种情况如果某行 pos 很大比如达到 n它能满足所有位置的要求贪心会优先使用它如果没有行能满足 needj 会越界到 n此时返回 -1。有的同学可能会问如果 pos[j] 比 need 大很多把它消耗在第 i 行是不是浪费比如 pos[j] n却让它放在了第 2 行是不是后面某行就缺一个能力值大的行导致失败这个问题我一开始也困惑过。答案是不会。因为第 i 行要求的能力阈值随着 i 增大单调递减。也就是说越靠后的位置要求能力越低。当前处理第 i 行时所有还没有被安排的行中如果最差的一行都能满足第 i 行的要求那么后续行也都能至少满足等于或者低于这个要求的阈值。反过来如果当前行失败说明剩余行里连一个满足当前阈值的都没有那么后面更不可能成功返回 -1 是正确的。所以在贪心过程中任何合法候选行放到当前位都不会影响后面的可行性。4. 常见问题、边界条件与实战避坑记录这道题虽然代码不长但我看到评论区里翻车的例子不少。整理几个高频问题和调试经验对你提交有用。4.1 为什么我的“后缀0长度”算成了整个行末尾0的长度却一直错有一个误区是把“后缀连续 0”算成了“从右往左数直到遇到 1 为止”这个方向没错但边界条件要注意。如果行为 [0, 0, 0, 0, 1]后缀 0 长度是 0 而不是 4因为最后一个元素不是 0。有的同学会把遍历条件写成for (int j n - 1; j 0 grid[i][j] 0; j--)这已经正确。但如果写成就数 0 出现次数再 break容易把中间的 1 漏掉因为需要从末位一步步往前。我建议先写最简单的遇到 1 就 break这样不会出错。4.2 交换次数为什么是 j - i而不是 j - i 加 1相邻交换的本质是把下标 j 的元素移动到下标 i需要跨过 j - i 个元素。比如 [A, B, C, D]想把 D 从位置 3 移到位置 0需要做的交换是 D 和 C 换1 次然后 D 和 B 换2 次然后 D 和 A 换3 次恰好是 3 3 - 0。不是 4因为你不需要跟“自己”交换。这个虽然是小学体育课排队的知识但我在代码里见过好几个人在这里 ans 多加一次。4.3 什么时候返回 -1最简单的情况grid 全 1那么所有行的 pos 都是 0。第 n-1 行要求 pos ≥ 1所以直接就不满足了返回 -1。除此之外还有一个隐蔽的情况即便前 i 行都安排好了处理到第 i 行时发现后面所有行都不满足 need那直接 -1。这里有一个快速判断的规律把所有行的 pos 值降序排列得到 sortedPos。如果 sortedPos[i] n - 1 - i 对任意 i 成立那么无论怎么交换都不可能成功。因为降序排列已经是最乐观的排列了它都满足不了的话其他排列更不可能。所以如果你想快速判断整体可行性可以先排序检查一遍但是那样会打乱后续的计数逻辑所以我更建议直接在贪心过程中判断遇到找不到就直接返回。4.4 有没有办法把复杂度降到 O(n)有人可能会想既然每一行的 pos 值只和所在行有关能不能用更快的办法跳过查找比如预处理一个数组 cnt[pos] 表示“后缀0长度恰好为 pos 的行有多少”然后从高到低分配位置。这个思路在计数型问题上很常见但这道题难在“最少相邻交换次数”不是一个简单的匹配问题而是需要保留原顺序信息数逆序对。比如两个行能力相同谁先谁后对可行性无影响但不同顺序会改变交换次数。所以不能用简单的计数桶跳过。最高效的做法是用一个平衡树维护剩余行的下标每次找到第一个满足条件的下标用 BIT 计算前面有多少个已移除元素从而通过逆序对计数得出答案。但 n ≤ 50 的情况下毫无必要。与其追求极端不如把 O(n^2) 的代码写对。4.5 一个自测样例这里给一个容易出错的测试用例你可以自己在本地跑grid [[1,0,0],[0,0,0],[1,1,0]]n3目标阈值分别是 [2, 1, 0]。第 0 行 pos 1因为末尾是 0倒数第二个是 1停止第 1 行 pos 3整行全 0第 2 行 pos 1末尾 0倒数第二个 1。处理第 0 行need2第 0 行 pos1 不满足第 1 行 pos3 满足所以把第 1 行交换到第 0 行需要 1 次。顺序变为 [3, 1, 1]。接着第 1 行 need1第 1 行 pos1 满足不动。第 2 行 need0任何行都满足。答案1。如果你不看 pos 信息直接模拟矩阵交换也能得到 1但一旦矩阵规模变大模拟就痛苦了。这个小例子说明抽象成 pos 数组后题目的维度立刻降了下来。5. 扩展思考这类“相邻交换最少次数”问题的通解套路LeetCode 1536 做完之后值得花一点时间把经验沉淀成模板。这类“通过相邻交换把序列变成满足某种约束的形态求最少次数”的问题在 LeetCode 上并不少见。比如 1053 交换一次的先前排列、1202 交换字符串中的元素、或者经典的选择排序式贪心求最小交换次数问题。它们的通解往往是三步第一步把目标序列的约束翻译成每个位置对元素的“要求”。这一步很重要很多时候约束不是“某个元素必须到某个位置”而是“某个位置的元素必须满足某个属性”。比如这道题是要求后缀 0 长度有些题是要求元素非递减、要求元素是奇数/偶数交替等。翻译得好后续就顺。第二步根据要求从左到右维护当前序列的合法性。每处理一个位置在剩余元素中找第一个或最好满足要求的元素把它移动到当前位置。最小相邻交换次数的计算公式就是 目标下标 - 当前下标可以通过平衡树或者数组模拟维护剩余元素的下标来避免实际移动。第三步如果在某一步找不到满足要求的元素返回 -1 或者根据题目要求返回特定值。我还想多说一个细节这类题目里如果把“找第一个满足要求的元素”换成“找最后一个满足要求的元素”答案往往不同。比如这道题要求阈值单调递减所以找第一个和找最后一个区别很大。找最后一个可能会让靠后的强能力行提前消耗导致后续局面的强能力行不足。这也是为什么在某些题解里会看到不同写法你要小心验证。回到这一题本身它在 LeetCode 上的难度是中等偏难难点并不是代码量而是建模。你能把二维矩阵里的“主对角线以下全为 0”翻译成一维的后缀 0 长度数组这道题就已经解掉大半了。剩下的是贪心证明和简单模拟。最后讲讲我个人做题时的习惯。我刷 LeetCode 很多题都有个固执的毛病在拿到一个“看似需要复杂操作”的题时先用 1 到 2 分钟徒手画出小样例甚至直接把矩阵在草稿纸上写出来找规律。这题我第一次做的时候上来就真的去模拟行交换结果写着写着发现自己一直在处理二维数组交换的细节思维被网格给困住了。后来把每行抽象成数字在纸上写下 pos 数组然后很快得到了贪心解法。从那以后凡是涉及矩阵重排的题我都会先问自己“这个操作的 invariant 是什么哪一行和哪一行之间的差异能用一个标量表示”如果答案是肯定的那么这道题十有八九会被降维打击。