Java C++算法题解leetcode801使序列递增的最小交换次数

前言LeetCode 801 的题意是给定两个长度相同的整数数组nums1和nums2每次操作可以交换某个下标 i 上的两个元素问最少交换多少次能使两个数组都严格递增。题目保证答案存在。这道题最容易掉进的坑是贪心看到某一对元素不满足递增就立刻交换或者看到交换后能让当前一对变好就交换。问题在于某个下标换不换会改变它与前一个下标、后一个下标之间的比较关系局部最优不一定通向全局最优。正确的做法是动态规划而且状态只需要两维当前下标「换」或「不换」。本文先说明为什么贪心不成立再推导两个状态的转移条件最后给出 C 的滚动数组实现和对应的 Java 版本。示例以 C17 为基准只使用标准库。一、为什么局部贪心会失败先看一个能用手算核对的例子nums1 [1, 3, 5, 4]nums2 [1, 2, 3, 7]。前三个位置已经不交换就满足递增问题出在最后一位nums1的 5 大于 4。此时交换下标 3得到[1, 3, 5, 7]与[1, 2, 3, 4]两个数组都严格递增答案是 1。如果规则改成「发现当前不递增就交换」在这个例子上也能得到正确答案。但换一组数据就会暴露问题有时当前这一对交换后仍然合法却会让下一对无法处理有时当前不交换看起来违反了递增但交换前一个位置反而能用更少的次数解决。也就是说决定第 i 位是否交换时必须同时知道第 i-1 位交换后的状态否则无法判断哪种选择可行。这就自然引出状态定义处理到下标 i 时只关心「i 换过」与「i 没换过」两种情况下各自的最小交换次数。更早的位置如何交换已经浓缩在这两个数值里。二、状态定义与转移条件设keep[i]表示「前缀 0 到 i 已经严格递增且下标 i 没有交换」时的最小交换次数swap[i]表示「前缀 0 到 i 已经严格递增且下标 i 交换了」时的最小交换次数。初始状态很直接keep[0] 0swap[0] 1。只有一个元素时不存在递增约束换或不换都合法代价分别是 0 和 1。考虑从 i-1 转移到 i。记a nums1[i-1]、b nums2[i-1]、c nums1[i]、d nums2[i]。第 i 位有两种选择第 i-1 位也有两种选择组合起来有四种但只有两种组合在几何上可能成立情况一i-1 和 i 都不交换。此时要求原来的两对都满足递增即a c且b d。满足时可以keep[i] keep[i-1]。情况二i-1 和 i 都交换。交换后第 i-1 位变成(b, a)第 i 位变成(d, c)。要求b d且a c与情况一的条件完全相同。满足时可以swap[i] swap[i-1] 1。情况三只有 i 交换i-1 不交换。此时第 i-1 位是(a, b)第 i 位是(d, c)要求a d且b c。满足时可以swap[i] keep[i-1] 1。情况四只有 i-1 交换i 不交换。第 i-1 位是(b, a)第 i 位是(c, d)要求b c且a d与情况三的条件相同。满足时可以keep[i] swap[i-1]。于是转移写成if (a c b d):keep[i] min(keep[i], keep[i-1])swap[i] min(swap[i], swap[i-1] 1)if (a d b c):keep[i] min(keep[i], swap[i-1])swap[i] min(swap[i], keep[i-1] 1)两个条件可能同时成立。例如两对元素本来就都递增交叉比较也成立时四种组合都可行这时要对每个状态取两种来源的最小值。只写其中一个条件是这道题最常见的错误。最终答案是min(keep[n-1], swap[n-1])因为最后一位换或不换都可能成为最优解。用前面的例子[1, 3, 5, 4]与[1, 2, 3, 7]推演i条件keepswap0初始01113、12 与 12、13 都成立01235、23 成立33 不成立02354 不成立57、34 成立21最后一行i 3算完后答案是min(2, 1) 1与手算一致。注意 i 1 时两个条件同时成立因此swap可以保持 1而不是简单地在上一轮基础上加一。三、C 与 Java 实现状态只依赖前一位因此不需要保存整个数组用两个变量滚动即可。注意在更新keep和swap之前必须先把新值算到临时变量里否则第二个条件会读到已经被覆盖的旧状态。// 适用于 C17#include algorithm#include iostream#include vectorint minSwap(const std::vectorint nums1, const std::vectorint nums2) {const int n static_castint(nums1.size());if (n 1) return 0;const int INF n 1; // 最多交换 n 次n1 足够表示不可达int keep 0; // i 0 不交换int swap 1; // i 0 交换for (int i 1; i n; i) {int next_keep INF;int next_swap INF;const int a nums1[i - 1];const int b nums2[i - 1];const int c nums1[i];const int d nums2[i];if (a c b d) {next_keep std::min(next_keep, keep);next_swap std::min(next_swap, swap 1);}if (a d b c) {next_keep std::min(next_keep, swap);next_swap std::min(next_swap, keep 1);}keep next_keep;swap next_swap;}return std::min(keep, swap);}int main() {std::vectorint a {1, 3, 5, 4};std::vectorint b {1, 2, 3, 7};std::cout minSwap(a, b) \n; // 按推导应当是 1return 0;}几个实现细节INF取n 1而不是INT_MAX是为了避免swap 1时符号溢出。有符号整数溢出是未定义行为undefined behavior, UB不能指望它回绕成负数。如果某个状态不可达它保持INF参与min也不会被选中INF 1虽然大于INF但仍在int范围内不会出问题。循环从 1 开始因此n 1时要单独返回 0否则keep/swap的初始值虽然也对但直接返回min(0, 1)同样是 0加这个判断只是让边界更明确。题目保证有解所以最终答案不会是INF如果用于其他场景应当检查结果是否等于INF并报告无解。对应的 Java 版本结构完全一致只是数组长度用length最小值用Math.min// 适用于 Java 8 及以上class Solution {public int minSwap(int[] nums1, int[] nums2) {int n nums1.length;if (n 1) return 0;int inf n 1;int keep 0;int swap 1;for (int i 1; i n; i) {int nextKeep inf;int nextSwap inf;if (nums1[i - 1] nums1[i] nums2[i - 1] nums2[i]) {nextKeep Math.min(nextKeep, keep);nextSwap Math.min(nextSwap, swap 1);}if (nums1[i - 1] nums2[i] nums2[i - 1] nums1[i]) {nextKeep Math.min(nextKeep, swap);nextSwap Math.min(nextSwap, keep 1);}keep nextKeep;swap nextSwap;}return Math.min(keep, swap);}}两种语言都只需要一次遍历时间复杂度 O(n)额外空间 O(1)。如果保留完整的keep与swap数组空间是 O(n)逻辑更直观适合在纸上推演提交时用滚动变量即可。常见坑点坑点一把严格递增写成非递减。❌if (a c b d)允许相等元素得到的结果对要求严格递增的题目是错的。✅ 题目要求严格递增所有比较都用。坑点二只写「同换/同不换」一种转移。❌ 只判断a c b d漏掉交叉条件遇到需要错位交换的用例会得到INF或偏大的值。✅ 同时处理a d b c的交叉情况。坑点三swap[0]初始化为 0。❌ 认为第一个位置不需要交换把两个初始状态都设成 0导致后续代价整体少算。✅keep[0] 0swap[0] 1。坑点四原地更新导致状态被覆盖。❌ 先写keep ...再用keep计算swap读到的是新值而不是 i-1 的值。✅ 用next_keep、next_swap暂存循环末尾统一赋值。坑点五用INT_MAX表示不可达再直接加一。❌swap INT_MAX; swap swap 1;有符号溢出属于 UB。✅ 用n 1作为哨兵或先判断是否可达再加。坑点六返回keep[n-1]。❌ 只考虑最后一位不交换忽略了「最后一位交换后更优」的情况。✅ 返回min(keep[n-1], swap[n-1])。坑点七循环下标从 0 开始却访问i-1。❌for (int i 0; ...)中访问nums1[i-1]越界。✅ 从 1 开始循环并单独处理n 1。坑点八把两个数组的长度当成可以不同。❌ 只读nums1.size()就越界访问nums2[i]题目保证等长但自定义测试时容易忽略。✅ 入口处断言或检查两者长度一致。总结要点内容状态keep[i]i 不换swap[i]i 换初始keep[0]0swap[0]1同序转移ac bdkeep 来自 keepswap 来自 swap1交叉转移ad bckeep 来自 swapswap 来自 keep1答案min(keep[n-1], swap[n-1])复杂度时间 O(n)空间 O(1)关键细节严格小于、两个条件都写、先算后赋值这道题的 DP 之所以成立是因为「是否交换第 i 位」只影响第 i 位与相邻位的比较不会改变更早前缀的合法性。把这一点想清楚两个转移条件就不是需要背诵的公式而是四种交换组合中真正可行的两种。