企业官网建设流程全解析

前言

LeetCode 801 的题意是：给定两个长度相同的整数数组nums1和nums2，每次操作可以交换某个下标 i 上的两个元素，问最少交换多少次，能使两个数组都严格递增。题目保证答案存在。

这道题最容易掉进的坑是贪心：看到某一对元素不满足递增，就立刻交换，或者看到交换后能让当前一对变好就交换。问题在于，某个下标换不换，会改变它与前一个下标、后一个下标之间的比较关系，局部最优不一定通向全局最优。正确的做法是动态规划，而且状态只需要两维：当前下标「换」或「不换」。

本文先说明为什么贪心不成立，再推导两个状态的转移条件，最后给出 C++ 的滚动数组实现和对应的 Java 版本。示例以 C++17 为基准，只使用标准库。

一、为什么局部贪心会失败

先看一个能用手算核对的例子：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] = 0，swap[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 = 3）算完后，答案是min(2, 1) = 1，与手算一致。注意 i = 1 时两个条件同时成立，因此swap可以保持 1，而不是简单地在上一轮基础上加一。

三、C++ 与 Java 实现

状态只依赖前一位，因此不需要保存整个数组，用两个变量滚动即可。注意在更新keep和swap之前，必须先把新值算到临时变量里，否则第二个条件会读到已经被覆盖的旧状态。

// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <vector>

int minSwap(const std::vector<int>& nums1, const std::vector<int>& nums2) {
const int n = static_cast<int>(nums1.size());
if (n <= 1) return 0;

const int INF = n + 1; // 最多交换 n 次，n+1 足够表示不可达
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::vector<int> a = {1, 3, 5, 4};
std::vector<int> b = {1, 2, 3, 7};
std::cout << minSwap(a, b) << '\n'; // 按推导应当是 1
return 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] = 0，swap[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]，题目保证等长，但自定义测试时容易忽略。

✅ 入口处断言或检查两者长度一致。

总结

这道题的 DP 之所以成立，是因为「是否交换第 i 位」只影响第 i 位与相邻位的比较，不会改变更早前缀的合法性。把这一点想清楚，两个转移条件就不是需要背诵的公式，而是四种交换组合中真正可行的两种。