801. 使序列递增的最小交换次数——medium-dp - 《leetcode》

我们有两个长度相等且不为空的整型数组 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]区间内的整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing

思路：
题目说明给定的输入总是有效的，在肯定有答案的情况下，不会出现 A=[4,3],B=[1,2] 这样的数据，对于A数组和B数组来说，相邻元素必然至少满足其中一种，否则通过交换无法得到答案：

A[i] > A[i - 1] && B[i] > B[i - 1]
A[i] > B[i - 1] && B[i] > A[i - 1]

1，2同时满足时有：

i交换,i-1可交换也可不交换，取较小值
i不交换，i-1可交换也可不交换，取较小值

只满足1时

i交换，i-1必须交换
i不交换，i-1必须不交换

只满足2时

i交换，i-1必须不交换
i不交换，i-1必须交换

复杂度分析：
时间复杂度O(n)
空间复杂度O(1) 使用滚动数组形式优化空间复杂度至O(1）

var minSwap = function (A, B) {
    let n = A.length;
    let [keep, swap] = [0, 1];
    for (let i = 1; i < n; i++) {
        if (A[i - 1] < A[i] && B[i - 1] < B[i]) {
            if (A[i - 1] < B[i] && B[i - 1] < A[i]) {
                [keep, swap] = [Math.min(keep, swap), Math.min(keep, swap) + 1];
            } else {
                [keep, swap] = [keep, swap + 1];
            }
        } else {
            [keep, swap] = [swap, keep + 1];
        }
    }
    return Math.min(keep, swap);
};