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

发表于 分类于 阅读次数： Waline： 本文字数： 971 阅读时长 ≈ 3 分钟

考点

  • 状态机DP

思路

题目概述

给定两个长度相同的整数数组 \[ A = (A_1, A_2, \dots, A_n),\quad B = (B_1, B_2, \dots, B_n) \] 允许在任意下标 \(i\) 处 同时交换 \(A_i\) 与 \(B_i\)。 目标是通过最少的交换次数，使得： \[ A_1 < A_2 < \dots < A_n,\quad B_1 < B_2 < \dots < B_n \]

一、动态规划建模

1. 状态定义

设 \[ f[i][0] = \text{处理前 } i \text{ 个位置，且第 } i \text{ 位不交换时的最小交换次数} \] 这里的关键在于： 状态不仅记录处理到哪里，还显式区分“当前位置是否交换”，以便对相邻位置的大小关系进行判断。

2. 初始状态（Base Case）

当 \(i = 1\) 时：

  • 若第 1 个位置 不交换： \[ f[1][0] = 0 \]

  • 若第 1 个位置 交换一次： \[ f[1][1] = 1 \]

这是本题最容易出错但也最关键的地方： 交换状态本身就代表一次操作，必须计入代价。

二、状态转移方程

考虑第 \(i\) 个位置（\(i \ge 2\)），有两类可能的递增关系。

情况一：不发生交叉（同态递增）

若满足： \[ A_i > A_{i-1} \quad \text{且} \quad B_i > B_{i-1} \] 说明在 交换状态保持一致 的前提下，仍能保持严格递增。

转移为： \[ \begin{aligned} f[i][0] &\leftarrow \min(f[i][0],\; f[i-1][0]) \\ f[i][1] &\leftarrow \min(f[i][1],\; f[i-1][1] + 1) \end{aligned} \] 解释：

  • 不换 → 不换：无需新增交换
  • 换 → 换：第 \(i\) 位交换一次，因此加 1

情况二：发生交叉（交叉递增）

若满足： \[ A_i > B_{i-1} \quad \text{且} \quad B_i > A_{i-1} \] 说明 当前是否交换 必须与 前一位是否交换相反，才能维持递增。

转移为： \[ \begin{aligned} f[i][0] &\leftarrow \min(f[i][0],\; f[i-1][1]) \\ f[i][1] &\leftarrow \min(f[i][1],\; f[i-1][0] + 1) \end{aligned} \] 解释：

  • 上一位换 → 当前不换
  • 上一位不换 → 当前换（新增一次交换）

状态转移小结

对每个 \(i\)，两种情况可以同时成立，因此所有满足条件的转移都必须取最小值。

三、结果计算（结尾处理）

当处理完全部 \(n\) 个位置后，最终答案为： \[ \min\bigl(f[n][0],\; f[n][1]\bigr) \] 即最后一位是否交换都可以，只需取总代价的最小值。

四、时间与空间复杂度

  • 时间复杂度： \[ O(n) \]

  • 空间复杂度： \[ O(n) \] （可进一步滚动优化为 \(O(1)\)）

五、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    static const int maxn = 1e5 + 5;
    static const int inf = INT_MAX >> 1;

    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        // f[i][0]: 前 i 个位置，第 i 位不交换的最小交换次数
        // f[i][1]: 前 i 个位置，第 i 位交换的最小交换次数
        int f[maxn][2];

        int n = nums1.size();

        // 初始化
        // 第 1 位不交换：0 次
        // 第 1 位交换：1 次
        f[1][0] = 0;
        f[1][1] = 1;

        // 状态转移
        for (int i = 2; i <= n; ++i) {
            f[i][0] = f[i][1] = inf;

            // 情况 1：同态递增（不交叉）
            if (nums1[i - 1] > nums1[i - 2] &&
                nums2[i - 1] > nums2[i - 2]) {

                // 不换 -> 不换
                f[i][0] = min(f[i][0], f[i - 1][0]);

                // 换 -> 换（第 i 位再交换一次）
                f[i][1] = min(f[i][1], f[i - 1][1] + 1);
            }

            // 情况 2：交叉递增
            if (nums1[i - 1] > nums2[i - 2] &&
                nums2[i - 1] > nums1[i - 2]) {

                // 上一位换 -> 当前不换
                f[i][0] = min(f[i][0], f[i - 1][1]);

                // 上一位不换 -> 当前换
                f[i][1] = min(f[i][1], f[i - 1][0] + 1);
            }
        }

        // 最终答案：最后一位换或不换取最小
        return min(f[n][0], f[n][1]);
    }
};

也可以滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e5 + 5, inf = INT_MAX >> 1;
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), a = 0, b = 1;
        for (int i = 2; i <= n; ++i) {
            int ta = inf, tb = inf;
            if (nums1[i - 1] > nums1[i - 2] && nums2[i - 1] > nums2[i - 2])
                ta = min(ta, a), tb = min(tb, b + 1);
            if (nums1[i - 1] > nums2[i - 2] && nums2[i - 1] > nums1[i - 2])
                ta = min(ta, b), tb = min(tb, a + 1);
            a = ta, b = tb;
        }
        return min(a, b);
    }
};