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

题目描述

这是 LeetCode 上的 801. 使序列递增的最小交换次数 ，难度为 困难。

我们有两个长度相等且不为空的整型数组 nums1 和 nums2。

在一次操作中，我们可以交换 $nums1[i]$ 和 $nums2[i]$ 的元素。

例如，如果 $nums1 = [1,2,3,8]$ ，$nums2 =[5,6,7,4]$ ，你可以交换 $i = 3$ 处的元素，得到 $nums1 =[1,2,3,4]$ 和 $nums2 =[5,6,7,8]$ 。

返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。

数组 arr 严格递增 且 $arr[0] < arr[1] < arr[2] < … < arr[arr.length - 1]$ 。

注意：

用例保证可以实现操作。

示例 1:

输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]

输出: 1

解释: 
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。

示例 2:

输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]

输出: 1

提示:

• $2 <= nums1.length <= 10^5$
• $nums2.length = nums1.length$
• $0 <= nums1[i], nums2[i] <= 2 * 10^5$

---

基本分析

这是一道很裸的状态机 DP 运用题。

由于每次交换只会发生在两数组的相同位置上，使得问题变得简单：仅需考虑交换当前位置后，当前元素与前后元素大小关系变化即可。

又因为我们会从前往后处理每个位置，因此只需要考虑当前位置与前一位置的大小关系即可。

---

状态机 DP

定义 $f[i][j]$ 为考虑下标范围为 $[0, i]$ 的元素，且位置 $i$ 的交换状态为 $j$ 时（其中 $j = 0$ 为不交换，$j = 1$ 为交换）两数组满足严格递增的最小交换次数。

最终答案为 $\min(f[n - 1][0], f[n - 1][1])$，同时我们有显而易见的初始化条件 $f[0][0] = 0$ 和 $f[0][1] = 1$，其余未知状态初始化为正无穷。

不失一般性考虑 $f[i][j]$ 该如何转移：

• 若 $nums1[i] > nums1[i - 1]$ 且 $nums2[i] > nums2[i - 1]$（即顺序位满足要求），此时要么当前位置 $i$ 和前一位置 $i - 1$ 都不交换，要么同时发生交换，此时有（分别对应两个位置「都不交换」和「都交换」）：

$$\begin{cases} f[i][0] = f[i - 1][0] \\ f[i][1] = f[i - 1][1] + 1 \end{cases}$$

• 若 $nums1[i] > nums2[i - 1]$ 且 $nums2[i] > nums1[i - 1]$（即交叉位满足要求），此时当前位置 $i$ 和前一位置 $i - 1$ 只能有其一发生交换，此时有（分别对应「前一位置交换」和「当前位置交换」）：

$$\begin{cases} f[i][0] = \min(f[i][0], f[i - 1][1]); \\ f[i][1] = \min(f[i][1], f[i - 1][0] + 1) \end{cases}$$

Java 代码：

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] f = new int[n][2];
        for (int i = 1; i < n; i++) f[i][0] = f[i][1] = n + 10;
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                f[i][0] = Math.min(f[i][0], f[i - 1][1]);
                f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1);
            }
        }
        return Math.min(f[n - 1][0], f[n - 1][1]);
    }
}

TypeScript 代码：

function minSwap(nums1: number[], nums2: number[]): number {
    const n = nums1.length
    const f = new Array<Array<number>>(n)
    f[0] = [0, 1]
    for (let i = 1; i < n; i++) f[i] = [n + 10, n + 10]
    for (let i = 1; i < n; i++) {
        if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
            f[i][0] = f[i - 1][0]
            f[i][1] = f[i - 1][1] + 1
        }
        if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
            f[i][0] = Math.min(f[i][0], f[i - 1][1])
            f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1)
        }
    }
    return Math.min(f[n - 1][0], f[n - 1][1])
}

Python 代码：

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        f = [[0, 0] for _ in range(n)]
        for i in range(1, n):
            f[i][0] = f[i][1] = n + 10
        f[0][1] = 1
        for i in range(1, n):
            if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:
                f[i][0], f[i][1] = f[i - 1][0], f[i - 1][1] + 1
            if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:
                f[i][0], f[i][1] = min(f[i][0], f[i - 1][1]), min(f[i][1], f[i - 1][0] + 1)
        return min(f[n - 1][0], f[n - 1][1])

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

滚动数组

利用 $f[i][X]$ 仅依赖于 $f[i - 1][X]$，我们可以采用「滚动数组」的方式，通过机械性操作将空间优化到 $O(1)$。

Java 代码：

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] f = new int[2][2];
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            int a = n + 10, b = n + 10;
            int prev = (i - 1) & 1, cur = i & 1; // 避免重复的 & 操作
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                a = f[prev][0];
                b = f[prev][1] + 1;
            }
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                a = Math.min(a, f[prev][1]);
                b = Math.min(b, f[prev][0] + 1);
            }
            f[cur][0] = a; f[cur][1] = b;
        }
        return Math.min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]);
    }
}

TypeScript 代码：

function minSwap(nums1: number[], nums2: number[]): number {
    const n = nums1.length
    const f = new Array<Array<number>>(2)
    f[0] = [0, 1], f[1] = [0, 0]
    for (let i = 1; i < n; i++) {
        let a = n + 10, b = n + 10
        const prev = (i - 1) & 1, cur = i & 1
        if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
            a = f[prev][0]
            b = f[prev][1] + 1
        }
        if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
            a = Math.min(a, f[prev][1])
            b = Math.min(b, f[prev][0] + 1)
        }
        f[cur][0] = a; f[cur][1] = b
    }
    return Math.min(f[(n - 1) & 1][0], f[(n - 1) & 1][1])
}

Python 代码：

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        f = [[0, 1], [0, 0]]
        for i in range(1, n):
            a, b = n + 10, n + 10
            prev, cur = (i - 1) & 1, i & 1
            if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:
                a, b = f[prev][0], f[prev][1] + 1
            if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:
                a, b = min(a, f[prev][1]), min(b, f[prev][0] + 1)
            f[cur][0], f[cur][1] = a, b
        return min(f[(n - 1) & 1][0], f[(n - 1) & 1][1])

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.801 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。