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
解释: 
交换 nums1[3] 和 nums2[3]。然后序列变为:
nums1 = [1, 3, 5, 7] 和 nums2 = [1, 2, 3, 4]
它们都是严格递增的。

示例 2:

输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
输出: 1

提示:

  • 2 <= nums1.length <= 10^5
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 2 * 10^5

解题思路

这是一道经典的动态规划问题。我们需要考虑在每个位置是否交换元素来使两个数组都严格递增。

核心思路：

定义状态：

  • keep[i] 表示在位置 i 不交换元素的情况下，前 i+1 个位置的最小交换次数
  • swap[i] 表示在位置 i 交换元素的情况下，前 i+1 个位置的最小交换次数

对于每个位置 i，我们需要分析两种情况：

  1. 当前位置满足递增条件：

    • 如果 nums1[i] > nums1[i-1] 且 nums2[i] > nums2[i-1]，说明不交换就能保持递增
    • 此时 keep[i] = keep[i-1]，swap[i] = swap[i-1] + 1

  2. 需要交换才能满足递增条件：

    • 如果 nums1[i] > nums2[i-1] 且 nums2[i] > nums1[i-1]，说明必须交换其中一个位置
    • 此时 keep[i] = swap[i-1]，swap[i] = keep[i-1] + 1

有些情况下两种条件都满足，我们需要取最小值。

通过空间优化，我们只需要维护前一个位置的状态即可。

代码实现

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int keep = 0, swap = 1;
        
        for (int i = 1; i < n; i++) {
            int keep2 = INT_MAX, swap2 = INT_MAX;
            
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                keep2 = min(keep2, keep);
                swap2 = min(swap2, swap + 1);
            }
            
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                keep2 = min(keep2, swap);
                swap2 = min(swap2, keep + 1);
            }
            
            keep = keep2;
            swap = swap2;
        }
        
        return min(keep, swap);
    }
};

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        keep, swap = 0, 1
        
        for i in range(1, n):
            keep2, swap2 = float('inf'), float('inf')
            
            if nums1[i] > nums1[i-1] and nums2[i] > nums2[i-1]:
                keep2 = min(keep2, keep)
                swap2 = min(swap2, swap + 1)
            
            if nums1[i] > nums2[i-1] and nums2[i] > nums1[i-1]:
                keep2 = min(keep2, swap)
                swap2 = min(swap2, keep + 1)
            
            keep, swap = keep2, swap2
        
        return min(keep, swap)

public class Solution {
    public int MinSwap(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        int keep = 0, swap = 1;
        
        for (int i = 1; i < n; i++) {
            int keep2 = int.MaxValue, swap2 = int.MaxValue;
            
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                keep2 = Math.Min(keep2, keep);
                swap2 = Math.Min(swap2, swap + 1);
            }
            
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                keep2 = Math.Min(keep2, swap);
                swap2 = Math.Min(swap2, keep + 1);
            }
            
            keep = keep2;
            swap = swap2;
        }
        
        return Math.Min(keep, swap);
    }
}

var minSwap = function(nums1, nums2) {
    const n = nums1.length;
    let keep = 0, swap = 1;
    
    for (let i = 1; i < n; i++) {
        let keep2 = Infinity, swap2 = Infinity;
        
        if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
            keep2 = Math.min(keep2, keep);
            swap2 = Math.min(swap2, swap + 1);
        }
        
        if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
            keep2 = Math.min(keep2, swap);
            swap2 = Math.min(swap2, keep + 1);
        }
        
        keep = keep2;
        swap = swap2;
    }
    
    return Math.min(keep, swap);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目