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

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

题目传送门

点击这里

解题思路

这道题的思维角度是有一定难度的，首先第一步思考就比较难，要理解只存在两种情况可以进行交换来满足题意的严格递增，第一种情况，nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]，第二种情况，nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]，需要满足这二者其一才可能进行交换，所以我们要考虑相邻元素之间的大小对比关系，这里就很像动态规划的状态转移方程，但是我们如果使用动态规划，还需要一个维度用来记录当前位置是否进行交换，所以dp[i][0]表示的是i位置不进行交换，dp[i][1]表示的是i位置进行交换，具体表示的值是最小操作次数，所以我们可以得出，如果满足第一种情况，dp[i][0] = dp[i-1][0]，dp[i][1] = dp[i-1][1] + 1，位置i的情况和i-1的情况一直如果满足第二种情况，dp[i][0] = dp[i-1][1]，dp[i][1] = dp[i-1][0] + 1，这个表示可以交换i-1位置也可以交换i位置，如果两种情况都满足，则取小值即可。这里可以看出每一个状态都和前一个状态有关，所以可以用滚动数组优化。

代码

func minSwap(nums1 []int, nums2 []int) int {
    n := len(nums1)
    dp := make([][2]int, n)
    dp[0][0], dp[0][1] = 0, 1
    for i := 1;i < n;i ++ {
        dp[i] = [2]int{n, n}
        if nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i] {
            dp[i][0] = dp[i-1][0]
            dp[i][1] = dp[i-1][1] + 1
        }
        if nums2[i-1] < nums1[i] && nums1[i-1] < nums2[i] {
            dp[i][0] = min(dp[i][0], dp[i-1][1])
            dp[i][1] = min(dp[i][1], dp[i-1][0] + 1)
        }
    }
    return min(dp[n-1][0], dp[n-1][1])
}

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

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

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