LeetCode 801. 使序列递增的最小交换次数

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 801. 使序列递增的最小交换次数

思路分析

解法一：动态规划（推荐）

核心思路：

用两个状态表示位置 i 时的最小交换次数：keep[i] 表示第 i 位不交换，swap[i] 表示第 i 位交换

状态转移时，若 nums1[i] > nums1[i-1] 且 nums2[i] > nums2[i-1]（同时满足不交换条件），则不交换可由上一位不交换转移，交换可由上一位交换转移

若 nums1[i] > nums2[i-1] 且 nums2[i] > nums1[i-1]（满足交叉条件），则可以互相转移，取两者最小值

两种条件可以同时成立，最终答案为 min(keep[n-1], swap[n-1])

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，只需遍历一次

空间复杂度：O(1)，只需常数级别的额外空间

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;

        // keep 表示当前位置不交换时的最小次数，swap 表示交换时的最小次数
        int keep = 0;
        int swap = 1;

        for (int i = 1; i < n; i++) {
            int newKeep = Integer.MAX_VALUE;
            int newSwap = Integer.MAX_VALUE;

            // 同位置不交换条件：两个数组各自保持递增
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                newKeep = Math.min(newKeep, keep);
                newSwap = Math.min(newSwap, swap + 1);
            }

            // 交叉条件：交换后仍满足递增
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                newKeep = Math.min(newKeep, swap);
                newSwap = Math.min(newSwap, keep + 1);
            }

            keep = newKeep;
            swap = newSwap;
        }

        return Math.min(keep, swap);
    }
}

func minSwap(nums1 []int, nums2 []int) int {
    n := len(nums1)

    // keep 表示当前位置不交换时的最小次数，swap 表示交换时的最小次数
    keep := 0
    swap := 1

    for i := 1; i < n; i++ {
        newKeep := math.MaxInt32
        newSwap := math.MaxInt32

        // 同位置不交换条件：两个数组各自保持递增
        if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] {
            if keep < newKeep {
                newKeep = keep
            }
            if swap+1 < newSwap {
                newSwap = swap + 1
            }
        }

        // 交叉条件：交换后仍满足递增
        if nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1] {
            if swap < newKeep {
                newKeep = swap
            }
            if keep+1 < newSwap {
                newSwap = keep + 1
            }
        }

        keep = newKeep
        swap = newSwap
    }

    if keep < swap {
        return keep
    }
    return swap
}

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	动态规划
123. 买卖股票的最佳时机 III	困难	动态规划
188. 买卖股票的最佳时机 IV	困难	动态规划
714. 买卖股票的最佳时机含手续费	中等	动态规划
309. 买卖股票的最佳时机含冷冻期	中等	动态规划
1567. 乘积为正数的最长子数组长度	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/82077393