【2022-10-10每日一题】801. 使序列递增的最小交换次数[Hard]

2022-10-10每日一题：801. 使序列递增的最小交换次数

难度：Hard

标签：数组 、 动态规划

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

方法一：动态规划

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func minSwap(nums1 []int, nums2 []int) int {
    n := len(nums1)
    a, b := 0, 1
    for i := 1; i < n; i++ {
        at, bt := a, b
        a, b = n, n
        if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] {
            a = min(a, at) // 不交换
            b = min(b, bt+1) // 交换
        }
        if nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1] {
            a = min(a, bt) // 不交换
            b = min(b, at+1) // 交换
        }
    }
    return min(a, b)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 nums1和 nums2的长度。需要遍历两个数组一次，每个状态的计算时间是 O(1)。
• 空间复杂度：O(1)。使用「滚动数组」后，仅使用常量空间。

LeetCode题库地址

• https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing