LeetCode 801. 使序列递增的最小交换次数

2022-04-14 HGNULB 约 14 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 801. 使序列递增的最小交换次数

题意分析

给定两个等长数组 nums1 和 nums2，每次操作可以选一个下标 $i$，把 nums1[i] 与 nums2[i] 互换。目标是让两个数组同时变成严格递增，求最少的操作次数。题目保证输入一定有解。

「只能交换同一下标上的两个元素」是这道题的骨架。它意味着每个位置只有两种独立的状态——换或不换，一共 $2^n$ 种方案。但相邻位置之间存在耦合：位置 $i$ 换不换，会改变它给位置 $i+1$ 留下的「前一位是多少」，从而影响后者的合法性。局部二选一 + 只与相邻位耦合，这个结构几乎是在直说答案是一维状态机型的动态规划。

「严格递增」要读准：是严格大于，不允许相等。所有比较必须用 $>$ 而不是 $\ge$。这一处漏改就会在含重复值的用例上出错。

「保证有解」这句话很有分量。它省掉了「无解返回什么」的分支，更重要的是它保证了递推过程中每个位置至少有一种合法选择，从而两个状态值永远不会同时变成无穷大——后面会看到，这一点让「无穷大参与加法」的溢出风险从根本上被排除。

约束是 $2 \le n \le 10^5$，元素值在 $[0, 2 \times 10^5]$ 内。$n$ 到十万，排除了任何指数级枚举和 $O(n^2)$ 做法；线性一次扫描是唯一目标。数值范围也提示答案最大不超过 $n$，用普通整型存储绰绰有余。

边界方面：第 0 个位置无论换不换都不违反任何约束（它前面没有元素），所以两种状态都是可达的；最终答案要在「最后一位换」和「最后一位不换」两种结局里取较小值，不能只看其中一种。

解法：动态规划（keep / swap）

核心思路

暴力是枚举每个位置换或不换的 $2^n$ 种组合，逐一验证两数组是否递增。$n = 10^5$ 时完全不可行。瓶颈在于：不同的组合之间存在大量重复的子结构——只要「前 $i$ 位已经合法」且「第 $i$ 位换没换」相同，前面具体怎么换对后续决策毫无影响。这正是可以做动态规划的信号。

于是显式写下状态定义：

$keep_i$ 表示「前 $i+1$ 个位置都已满足严格递增，且第 $i$ 位没有交换」时所需的最小交换次数；$swap_i$ 表示同样条件下第 $i$ 位已经交换时所需的最小交换次数。

注意状态里必须包含「第 $i$ 位换没换」这一维。如果只记「前 $i$ 位合法的最小交换次数」，信息就不足了——因为下一位能否放置，取决于当前位最终留下的是哪两个值，而这由换没换决定。这是本题最核心的建模决策。

初始值：$keep_0 = 0$（第 0 位不换，零次操作），$swap_0 = 1$（第 0 位换，一次操作）。两者都合法，因为单个位置不受任何递增约束。

转移时，位置 $i$ 与 $i-1$ 的组合共有四种（各自换或不换），但它们的合法性只由两个条件决定：

条件 A（同位递增）：$nums1[i] > nums1[i-1]$ 且 $nums2[i] > nums2[i-1]$。它描述的是「$i$ 与 $i-1$ 的交换状态相同」时是否合法——两个都不换，比较的就是原始的两对；两个都换，比较的是互换后的两对，而互换后 nums1 那条链上放的是原 nums2 的值、nums2 链上放的是原 nums1 的值，两条链各自的比较关系与「都不换」完全一致。所以同一个条件同时管住了「都不换」和「都换」。

条件 B（交叉递增）：$nums1[i] > nums2[i-1]$ 且 $nums2[i] > nums1[i-1]$。它描述的是「$i$ 与 $i-1$ 的交换状态相反」时是否合法——$i-1$ 换而 $i$ 不换，则 nums1 链上是 $nums2[i-1]$ 与 $nums1[i]$ 比、nums2 链上是 $nums1[i-1]$ 与 $nums2[i]$ 比；$i-1$ 不换而 $i$ 换，则两条链上的比较对完全相同，只是所属数组对调。所以同一个条件也同时管住了两种「状态相反」的情形。

把四种组合按条件归类，转移就写完了：

若条件 A 成立：$keep_i \leftarrow keep_{i-1}$（都不换，本位不加操作），$swap_i \leftarrow swap_{i-1} + 1$（都换，本位加一次操作）。

若条件 B 成立：$keep_i \leftarrow swap_{i-1}$（前一位换、本位不换），$swap_i \leftarrow keep_{i-1} + 1$（前一位不换、本位换）。

两个条件可能同时成立，此时对每个新状态取两条来路的较小值；也可能只成立一个；题目保证有解，所以不会两个都不成立。

初值方面，每轮先把两个新状态置为一个足够大的哨兵，只有条件成立时才用来路去更新。由于至少一个条件成立，且旧的 $keep$、$swap$ 都是有限值（可由归纳法从初值推出），新状态不会保留哨兵值，所以 $swap_{i-1} + 1$ 这类加法永远不会在无穷大上执行——这正是「保证有解」带来的隐性安全保障。

转移只依赖 $i-1$ 这一层，所以不需要开数组，两个标量滚动即可。但必须用新旧两组变量：$keep_i$ 与 $swap_i$ 都要读旧的 $keep_{i-1}$ 和 $swap_{i-1}$，如果原地更新，先算出的新 $keep$ 会污染后算的新 $swap$。

最终答案是 $\min(keep_{n-1},\ swap_{n-1})$——最后一位换或不换都可以，取较优的那个。

解题步骤

第一步，初始化 $keep = 0$、$swap = 1$。 为什么两个都要有初值而不是只设 $keep = 0$：第 0 位交换也是一种合法起点，且可能是最优路径的开端。只设一个会让整条「从换开始」的路径被丢掉。

第二步，从 $i = 1$ 遍历到 $n-1$，每轮先把 $newKeep$、$newSwap$ 置为哨兵大值。 为什么要重置：这两个变量代表本轮的最优值，必须从「尚无可行来路」开始，由成立的条件逐个更新。沿用上一轮的值会把非法转移当成合法。

第三步，检查条件 A：$nums1[i] > nums1[i-1]$ 且 $nums2[i] > nums2[i-1]$。成立则 $newKeep \leftarrow \min(newKeep,\ keep)$、$newSwap \leftarrow \min(newSwap,\ swap + 1)$。 为什么同一个条件同时喂给两个状态：条件 A 刻画的是「相邻两位交换状态相同」时的合法性，「都不换」和「都换」这两种组合共享它。为什么 $newSwap$ 要加一：本位执行了一次交换，操作数加一；而 $newKeep$ 不加，因为本位没动。

第四步，检查条件 B：$nums1[i] > nums2[i-1]$ 且 $nums2[i] > nums1[i-1]$。成立则 $newKeep \leftarrow \min(newKeep,\ swap)$、$newSwap \leftarrow \min(newSwap,\ keep + 1)$。 为什么来路交叉：条件 B 对应「相邻两位交换状态相反」，所以本位不换就得配前一位换（取 $swap$），本位换就得配前一位不换（取 $keep$）。这个交叉关系写反是本题最高频的错误。

第五步，把 $newKeep$、$newSwap$ 赋回 $keep$、$swap$，进入下一轮。 为什么必须等两个都算完再一起赋值：两个转移都读旧值，原地更新会让第二个读到已被覆盖的新值。

第六步，返回 $\min(keep,\ swap)$。 为什么不能只返回 $keep$：最优方案完全可能以「最后一位交换」结尾。

以 nums1 = [1, 3, 5, 4]、nums2 = [1, 2, 3, 7] 走一遍（$n = 4$，期望答案 1）。

初始化：$keep = 0$、$swap = 1$。

$i = 1$（比较 $(3,2)$ 与 $(1,1)$）：
条件 A：$3 > 1$ 且 $2 > 1$，成立。$newKeep = \min(\infty,\ keep) = 0$；$newSwap = \min(\infty,\ swap + 1) = 2$。
条件 B：$3 > nums2[0] = 1$ 且 $2 > nums1[0] = 1$，也成立。$newKeep = \min(0,\ swap) = \min(0, 1) = 0$；$newSwap = \min(2,\ keep + 1) = \min(2, 1) = 1$。
更新后 $keep = 0$、$swap = 1$。含义是：前两位若都不换，零次操作即可；若第 1 位换，最少一次操作（第 0 位不换、第 1 位换）。

$i = 2$（比较 $(5,3)$ 与 $(3,2)$）：
条件 A：$5 > 3$ 且 $3 > 2$，成立。$newKeep = \min(\infty,\ 0) = 0$；$newSwap = \min(\infty,\ 1 + 1) = 2$。
条件 B：$5 > nums2[1] = 2$ 成立，但 $nums2[2] = 3 > nums1[1] = 3$ 不成立（严格大于，相等不算），条件 B 失败。这一步正好演示了严格递增的判定——若误写成 $\ge$，条件 B 会被误判为成立，$newSwap$ 会被更新成 $keep + 1 = 1$，后面的结果就全乱了。
更新后 $keep = 0$、$swap = 2$。

$i = 3$（比较 $(4,7)$ 与 $(5,3)$）：
条件 A：$nums1[3] = 4 > nums1[2] = 5$ 不成立，条件 A 失败。
条件 B：$nums1[3] = 4 > nums2[2] = 3$ 成立，$nums2[3] = 7 > nums1[2] = 5$ 成立，条件 B 成立。$newKeep = \min(\infty,\ swap) = 2$；$newSwap = \min(\infty,\ keep + 1) = 1$。
更新后 $keep = 2$、$swap = 1$。

返回 $\min(2, 1) = 1$。

验证一下这个 1 对应的方案：只交换最后一位。交换后 nums1 = [1,3,5,7]、nums2 = [1,2,3,4]，两者都严格递增，恰好一次操作。这个例子里 $i = 3$ 的两个状态来源完全交叉——本位换配前位不换（花费 $0 + 1 = 1$）、本位不换配前位换（花费 $2$），正是条件 B 的两条来路，把交叉关系写反就会得到 3 而不是 1。

代码实现

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int keep = 0;
        int swap = 1;

        for (int i = 1; i < n; i++) {
            int newKeep = Integer.MAX_VALUE;
            int newSwap = Integer.MAX_VALUE;

            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                newKeep = Math.min(newKeep, keep);
                newSwap = Math.min(newSwap, swap + 1);
            }

            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                newKeep = Math.min(newKeep, swap);
                newSwap = Math.min(newSwap, keep + 1);
            }

            keep = newKeep;
            swap = newSwap;
        }

        return Math.min(keep, swap);
    }
}

func minSwap(nums1 []int, nums2 []int) int {
    n := len(nums1)

    keep := 0
    swap := 1

    for i := 1; i < n; i++ {
        newKeep := 1 << 30
        newSwap := 1 << 30

        if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] {
            if keep < newKeep {
                newKeep = keep
            }
            if swap+1 < newSwap {
                newSwap = swap + 1
            }
        }

        if nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1] {
            if swap < newKeep {
                newKeep = swap
            }
            if keep+1 < newSwap {
                newSwap = keep + 1
            }
        }

        keep = newKeep
        swap = newSwap
    }

    if keep < swap {
        return keep
    }
    return swap
}

复杂度分析

时间复杂度：$O(n)$。一次线性扫描，每个位置做两次条件判断（各含两次比较）和至多四次取最小值，全是常数操作。$n = 10^5$ 时不到百万次基本运算。

空间复杂度：$O(1)$。虽然本质上是动态规划，但每层只依赖上一层，用四个整型标量（两个旧状态、两个新状态）就够，不需要开长度为 $n$ 的数组。这是状态机型 DP 的典型收益——状态维度是常数，天然可以滚动。

关键点总结

决策会影响后继约束时，把决策本身编进状态。「前 $i$ 位合法的最小代价」不足以决策，因为下一位能否放置取决于当前位最终的取值。加上「当前位换没换」这一维之后，状态就自足了。凡是遇到「每个位置二选一且相邻耦合」，都应该条件反射地设两个状态。

把四种组合归并成两个条件，是本题的化简关键。「同状态」共享条件 A、「异状态」共享条件 B，原因是交换操作对两条链的作用是对称的。能看出这层对称性，代码就从四个分支缩成两个；看不出也不影响正确性，但会写得冗长且容易漏。

交叉来路必须与条件对应：条件 B 成立时，本位不换要接前位换的状态，本位换要接前位不换的状态。这个交叉是本题最容易写反的地方，检验方法是问自己「这两位的交换状态是相同还是相反」。

滚动更新必须分离新旧。两个新状态都读旧的两个值，原地写会互相污染。判断标准和所有滚动数组一样：本轮的写入会不会被本轮的读取用到。

「保证有解」是一个可以依赖的前提。它保证每轮至少一个条件成立，从而两个状态永远有限，哨兵值不会参与加法。反过来说，如果题目不保证有解，就必须在加一之前检查旧状态是否为哨兵，否则会溢出。读题时要专门留意这类隐含的安全保证。

面试视角：这题的关键陈述是「只知道前 $i$ 位的最小代价不够，还要知道第 $i$ 位换没换」。把这句话说出来，面试官基本就认可你抓住了考点。接下来要能推导出两个条件为什么各自覆盖两种组合——这一步体现你不是背下来的。常见追问有两个：一是「初值为什么 $swap = 1$」，答案是第 0 位交换合法且要计一次操作；二是「为什么最后取两者最小」，答案是最后一位换或不换都可以收尾。如果面试官问「不保证有解怎么办」，要能答出：转移前需判断旧状态是否为哨兵，且最终两个状态都是哨兵时返回 $-1$。

易错点总结

错误写法：条件 B 成立时来路不交叉，写成 $newKeep \leftarrow keep$、$newSwap \leftarrow swap + 1$。以 nums1 = [1,3,5,4]、nums2 = [1,2,3,7] 为例，$i = 3$ 时条件 A 失败、只有条件 B 成立，正确的 $newSwap$ 应取 $keep + 1 = 1$，写错后取 $swap + 1 = 3$，最终返回 3，而正确答案是 1。这是本题第一大错误。

错误写法：比较用 $\ge$ 而非 $>$。以 nums1 = [1,3,5,4]、nums2 = [1,2,3,7] 为例，$i = 2$ 时 $nums2[2] = 3$ 与 $nums1[1] = 3$ 相等，用 $\ge$ 会让条件 B 被误判为成立，$swap$ 变成 1 而非 2，后续结果全部偏离。题目要求的是严格递增。

错误写法：条件 B 写成 $nums1[i] > nums1[i-1]$ 且 $nums2[i] > nums2[i-1]$ 的取反。以 nums1 = [0,4,4,5,9]、nums2 = [0,1,6,8,10] 为例，两个条件可以同时成立（$i = 1$ 处 $4 > 0$、$1 > 0$ 且 $4 > 0$、$1 > 0$），它们不是互斥关系而是各自独立判定。用取反会漏掉大量合法转移。

错误写法：原地更新，先写 keep = ... 再用 keep 算 swap。以 nums1 = [1,3,5,4]、nums2 = [1,2,3,7] 为例，$i = 3$ 时先把 $keep$ 更新成 2，随后条件 B 的 $newSwap = keep + 1$ 读到的是新值 3 而非旧值 0，返回 2 而正确答案是 1。两个状态必须同时切换。

错误写法：每轮不重置 $newKeep$、$newSwap$，直接在旧值上取最小。以 $i$ 处条件 A 失败、条件 B 成立的位置为例，$newKeep$ 会保留上一轮的值而不是被本轮唯一的合法来路覆盖，等于允许了一次非法转移，答案偏小。

错误写法：初始化 $swap = 0$。以 nums1 = [1,3,5,4]、nums2 = [1,2,3,7] 为例，第 0 位交换却不计操作数，最终返回 0，而正确答案是 1。$swap$ 的语义是「第 0 位已交换」，那一次操作必须计入。

错误写法：只返回 $keep$。以 nums1 = [1,3,5,4]、nums2 = [1,2,3,7] 为例，最优方案是交换最后一位，$keep = 2$ 而 $swap = 1$，只返回 $keep$ 得 2，正确答案是 1。收尾时两种状态都合法。

错误写法：认为「哪边小就换哪边」的贪心可行。以 nums1 = [0,4,4,5,9]、nums2 = [0,1,6,8,10] 为例，贪心地在每个违反递增的位置立刻交换，会因为忽略了交换对后续位置的连锁影响而多做操作；正确答案是 1，贪心往往给出更大的值。局部最优不导出全局最优。

错误写法：条件 A 只检查 nums1，忘记同时检查 nums2。以 nums1 = [1,6]、nums2 = [5,2] 为例，$i = 1$ 时 $nums1$ 满足 $6 > 1$ 但 $nums2$ 的 $2 > 5$ 不成立，条件 A 实际失败；漏检会让「都不换」被误判为合法，$newKeep$ 取到 $keep = 0$，最终返回 0，而正确答案是 1（必须交换其中一位）。两个数组必须同时递增。

错误写法：题目不保证有解时沿用本代码。若某轮两个条件都不成立，$newKeep$ 与 $newSwap$ 都保持哨兵值；下一轮若条件 A 成立，会执行 Integer.MAX_VALUE + 1 溢出成负数，min 把这个负值选走，最终返回一个负数。本题因保证有解而安全，迁移到无保证的变体时必须补上哨兵判断。

错误写法：把状态定义成「前 $i$ 位合法的最小交换次数」这一个值。以 nums1 = [1,3,5,4]、nums2 = [1,2,3,7] 为例，走到 $i = 3$ 时只知道「前三位最少 0 次」，却不知道第 2 位当前留下的是 5 还是 3，无法判断 4 能否接上，转移根本写不出来。状态必须含交换标记。

错误写法：交换操作被理解成「可以交换任意两个位置的元素」。以任意输入为例，这会让问题变成完全不同的排序类问题，答案与本题无关。题目限定只能交换同一下标上的两个元素。

相似题目

题目	难度	考察点
926. 将字符串翻转到单调递增	中等	同为两状态机 DP，状态是「当前位翻成 0 还是 1」，转移只有前缀约束无交叉
376. 摆动序列	中等	状态是「上一步是升还是降」，同样靠两个滚动变量，但求的是最长而非最少
309. 买卖股票的最佳时机含冷冻期	中等	三状态机 DP，训练「把决策编进状态」的同一套建模方法
123. 买卖股票的最佳时机 III	困难	状态维度扩到「交易次数 × 持仓与否」，是本题状态设计思路的进阶
198. 打家劫舍	中等	「选或不选」的两状态入门题，相邻耦合但无交叉转移
665. 非递减数列	中等	同样要求序列递增，但只允许改一个元素且用贪心判定，可对照 DP 与贪心的适用界
714. 买卖股票的最佳时机含手续费	中等	两状态滚动更新，操作代价体现在转移的加法项上，与本题的「加一」同构
LCR 092. 将字符串翻转到单调递增	中等	与 926 同题，可用来巩固两状态滚动的写法