题目描述
这是 力扣上的 801. 使序列递增的最小交换次数，难度为 困难。
题目分析
根据题目要求，我们知道题目给出的 num1 和 nums2 长度一致，需要我们通过交换其对应位置上的值，来达到 nums1 和 nums2 严格单调递增，题目要求我们找到最少的交换次数，就可以达到这个目的
简单看题目中给出的描述和给出的示例，我们是否就是简单的遍历一下给出的数组，发现要是可以交换的话，那么就给他们交换就好了呗？
说的对，可是又不完全对
思考：
此处我们需要考虑两个事情，交换 nums1nums1nums1 和 nums2nums2nums2 对应位置上数据的条件是什么？
要考虑，如何才能做到交换次数最小？
那么，很明显，咱们考虑这个问题，更多的是要考虑每一个位置上的数据，换还是不换 这两种状态
我们可以定义 help 二维数组，
- help[i][0] 表示到当前位置为止， i 位置不交换的情况下的交换次数
- help[i][1] 表示到当前位置为止， i 位置要交换的情况下的交换次数
那么nums1 nums1nums1 和 nums2nums2nums2 对应位置上的数字交换的条件是
第一种
有位置 i ，nums1[i]>nums1[i−1]且nums2[i]>nums2[i−1]nums1[i] > nums1[i-1] 且 nums2[i] > nums2[i-1]nums1[i]>nums1[i−1]且nums2[i]>nums2[i−1]
第二种
或者 nums1[i]>nums2[i−1]且nums2[i]>nums1[i−1]nums1[i] > nums2[i-1] 且 nums2[i] > nums1[i-1]nums1[i]>nums2[i−1]且nums2[i]>nums1[i−1]
第三种
又 或者 上述 两种情况都满足
对于第一种情况，相当于默认就已经是有序了，因此我们把 i 位置，和 i-1 位置上的值全部交换，要么就要不不交换，那么就有递推公式
help[i][0]=help[i−1][0]help[i][0] = help[i-1][0]help[i][0]=help[i−1][0]
help[i][1]=help[i−1][1]+1help[i][1] = help[i-1][1] +1help[i][1]=help[i−1][1]+1
对于上述第二种情况，实际上题目示例已经给出来了，满足这种交叉的情况
交叉的情况，咱们交换值的时候也有两种情况，那就是 i 位置上交换，则 i-1 位置上不交换，反之亦然：
help[i][0]=help[i−1][1]help[i][0] = help[i-1][1]help[i][0]=help[i−1][1]
help[i][1]=help[i−1][0]+1help[i][1] = help[i-1][0] + 1help[i][1]=help[i−1][0]+1
对于第三种情况
那就是上述 2 种情况都满足，实际上，我们就可以将第三种情况归类到第二种情况，相当于在第二种情况的时候，去处理一下最小值即可，会有 2 个 case：
- case1：满足第一种情况，且满足第二种情况
- case2：未满足第一种情况，但是满足了第二种情况
这两种 case 我们可以统一去取最小值就可以了：
help[i][0]=min(help[i][0],help[i−1][1])help[i][0] = min(help[i][0] , help[i-1][1])help[i][0]=min(help[i][0],help[i−1][1])
help[i][1]=min(help[i][1],help[i−1][0]+1)help[i][1] = min(help[i][1] ,help[i-1][0]+1)help[i][1]=min(help[i][1],help[i−1][0]+1)
此处如何去理解和处理呢？
我们默认help[0][0] = 0, help[1][0] =1 ，这个没啥好说的， 其他的值，默认写一个最大的值，例如 数组的长度 n，即 help[i][0]=help[i][1]=nhelp[i][0] = help[i][1] = nhelp[i][0]=help[i][1]=n
此时，对于上述 case1，上述的help[i][0] help[i][0]help[i][0] 和 help[i][1]help[i][1] help[i][1]就是一个经过运算之后的值，case2 的话 help[i][0]和help[i][1]help[i][0] 和 help[i][1]help[i][0]和help[i][1] 就是一个 n 值 ，这样，我们计算到我们期望的数据
接下来，咱们就可以来实现编码了，咱们这次使用 golang 的方式来进行实现
Golang 的实现方式：
func minSwap(nums1 []int, nums2 []int) int { // 重点考虑每一个位置上对应的元素，换 或者 不换 n := len(nums1) help := make([][]int, n) for i,_ := range help { help[i] =make([]int, 2) help[i][0], help[i][1] = n, n } // 第一个位置上的元素，如果换，那么就是交换了1 次，如果不换，那么就是交换了 0 次 help[0][0],help[0][1]= 0, 1 for i := 1;i<n; i++ { if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] { // i 和 i-1 要么一起换，要么一起不换 help[i][0] = help[i-1][0] help[i][1] = help[i-1][1] + 1 } if nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1] { // i 换，i-1 就不换，反之亦然 help[i][0] = min( help[i][0],help[i-1][1]) help[i][1] = min( help[i][1] ,help[i-1][0] +1) } } return min(help[n-1][0], help[n-1][1]) } func min(a , b int) int { if a < b { return a } return b }
这种实现方式，咱们的时间复杂度是 O(n)，此处的 n 是 nums1 的长度，空间复杂度是 O(n) ，此时其实咱们可以将上述的 help 数组变成滚动的方式，那么 空间复杂度就是 O(1) 了，因为每一次循环，咱们都仅仅是依赖上一次 help 数组中的内容
今天就到这里，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
