困难

问题描述

我们有两个长度相等且不为空的整型数组 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 <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 2 * 105

动态规划

由于题目限制用例保证可以实现操作，那么对于某个位置 $i$ 上的数，必然至少满足以下两种情况中的一种：

• $nums_1[i - 1] < nums_1[i] \text{且} nums_2[i - 1] < nums_2[i]$
• $nums_2[i - 1] < nums_1[i] \text{且} nums_1[i - 1] < nums_2[i]$

否则无论如何交换，都无法保证严格递增。 对于某个位置上的数交换和不交换两种情况，设 $dp[0][i]$ 表示到达位置 $i$ 时，不交换位置 $i$ 上的数保证严格递增的最小操作步数。$dp[1][i]$ 表示到达位置 $i$ 时，交换位置 $i$ 上的数保证严格递增的最小操作步数。

• 对于仅满足情况 1：
  • 不交换两个数已满足要求，因此 dp[0][i] = dp[0][i-1]，
  • 交换两个数，需要在 $i-1$ 位置时进行交换，交换后才能保证满足需求，因此 dp[1][i] = dp[1][i-1] + 1
• 对于仅满足情况 2：
  • 不交换两个数，需要在 $i-1$ 位置时进行交换，才能保证满足需求，因此 dp[0][i] = dp[1][i-1]
  • 交换两个数后满足要求，因此 dp[1][i] = dp[0][i-1] + 1
• 对于同时满足情况 1 和情况 2 的，直接取两种情况的最小值即可。

由于位置 $i$ 的状态只由 $i - 1$ 转移得到，一次可以使用滚动数组优化空间复杂度。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minSwap = function (nums1, nums2) {
  const n = nums1.length
  const dp = new Array(2).fill(0).map(() => new Array(2))
  dp[0][0] = 0
  dp[1][0] = 1
  for (let i = 1; i < n; i++) {
    let a = n
    let b = n
    if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
      a = Math.min(a, dp[0][(i - 1) & 1])
      b = Math.min(b, dp[1][(i - 1) & 1] + 1)
    }
    if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
      a = Math.min(a, dp[1][(i - 1) & 1])
      b = Math.min(b, dp[0][(i - 1) & 1] + 1)
    }
    dp[0][i & 1] = a
    dp[1][i & 1] = b
  }
  return Math.min(dp[0][(n - 1) & 1], dp[1][(n - 1) & 1])
}

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