题目描述

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

我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。

在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为 A[0] < A[1] < A[2] < ... < A[A.length - 1]）。

给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。

样例

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

提示

• A、B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
• A[i]、B[i] 均为 [0, 2000] 区间内的整数。

算法

(动态规划) $O(n)$

1. $f(i, 0)$ 表示使 A[0] 到 A[i] 和 B[0] 到 B[i] 严格单调递增，且 A[i] 没有与 B[i] 交换的的最小交换次数。
2. $f(i, 1)$ 表示使 A[0] 到 A[i] 和 B[0] 到 B[i] 严格单调递增，且 A[i] 有与 B[i] 交换的的最小交换次数。
3. 初始时 $f(i, j)$ 都是正无穷，但 $f(0, 0) = 0, f(0, 1) = 1$。
4. 转移时，如果 A[i] > A[i - 1] && B[i] > B[i - 1]，则 $f(i, 0) = min(f(i, 0), f(i - 1, 0)$，$f(i, 1) = min(f(i, 1), f(i - 1, 1) + 1)$，表示第 $i$ 位如果不交换，则与上一次从不交换转移；这一次交换，需要从上一次也交换转移。
5. 如果 A[i] > B[i - 1] && B[i] > A[i - 1]，则 $f(i, 0) = min(f(i, 0), f(i - 1, 1)$，$f(i, 1) = min(f(i, 1), f(i - 1, 0) + 1)$，表示第 $i$ 位如果不交换，则从上一次交换转移；这一次交换，需要从上一次不交换转移。
6. 最终答案为 $\min(f(n - 1, 0), f(n - 1, 1))$。

时间复杂度

• 状态数为 $O(n)$，每次转移仅需要常数时间，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的空间记录状态，也可以将这一部分空间优化掉，用两个变量替代这个数组进行转移。

C++ 代码

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<vector<int>> f(n, vector<int>(2, n + 1));
        f[0][0] = 0;
        f[0][1] = 1;

        for (int i = 1; i < n; i++) {
            if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
                f[i][0] = min(f[i][0], f[i - 1][0]);
                f[i][1] = min(f[i][1], f[i - 1][1] + 1);
            }

            if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
                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 - 1][0], f[n - 1][1]);
    }
};