题目描述
给了两个整型数组nums1和nums2，数组长度相等且不为空，定义了一个操作：可以交换两个数组中同索引的元素
如果要使nums1和nums2严格递增，问最小的操作次数？（用例保证可以实现操作）
基本分析
- 严格递增的定义？不包含等号
- 什么情况下需要交换？是不是两个数组中有一个会碰到一个逆序的，统计逆序的个数就行？不行，有可能a1<a2, b1<b2的时候也会交换；而交换前的状态会影响交换后的状态
- 严格递增包含了其他啥信息？只用考虑相邻元素的关系->可以从左到右递推关系，只不过不能只看逆序这么简单
- 单纯考虑逆序不行，应该怎么做？增加一个维度，用dp来做。具体怎么实现？
- 状态定义上怎么考虑？除了前i个元素i这个维度外，还要考虑i处元素是不是交换这个事情，再定义一个新的维度，值为0或者1，dp[i][0]表示不交换i处的元素时，前i个元素严格递增的最小操作次数，dp[i][1]表示交换i处的元素时，前一个元素严格递增的最小操作次数
- 转移上怎么考虑？因为只用考虑相邻关系，用a1、a2，b1，b2分别表示nums1[i-1], nums1[i], nums2[i-1]
, nums2[i]。会有以下情况：- a1<a2, b1<b2 这个时候可换可不换。不换时有f[i][0]=f[i-1][0], 换时有f[i][1]=f[i-1][1]+1, 注意这里的换是同时进行变换
- b1<a2, a1<b2 这个时候可以交换其中一对。前一个位置交换：f[i][0] = f[i-1][1], 后一个位置交换f[i][1] = f[i-1][0]+1
- 同时满足以上情况的时候，要取最小值
代码
f1-原始定义状态机dp
class Solution:
def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
f = [[inf, inf] for _ in range(n)]
f[0] = [0, 1]
for i in range(1, n):
a1, a2 = nums1[i-1], nums1[i]
b1, b2 = nums2[i-1], nums2[i]
if a1 < a2 and b1 < b2:
f[i][0] = f[i-1][0]
f[i][1] = f[i-1][1] + 1
if a1 < b2 and b1 < a2:
f[i][0] = min(f[i][0], f[i-1][1])
f[i][1] = min(f[i][1], f[i-1][0] + 1)
return min(f[-1])
f2-优化空间
class Solution:
def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
f = [[0, 1], [inf, inf]]
for i in range(n):
ns, s = inf, inf
a1, a2, b1, b2 = nums1[i-1], nums1[i], nums2[i-1], nums2[i]
prev, cur = (i-1)&1, i&1
if a1 < a2 and b1 < b2:
ns, s = f[prev][0], f[prev][1]+1
if a1 < b2 and b1 < a2:
ns, s = min(ns, f[prev][1]), min(s, f[prev][0]+1)
f[cur][0], f[cur][1] = ns, s
return min(f[(n-1)&1][0], f[(n-1)&1][1])
复杂度
时间：n是数组长度，需要遍历两个数组一次，为\(O(n)\)
空间：如果使用滚动数组，是常量空间\(O(1)\)
总结
- 题意和逆序的关系？（1）不是只有逆序才能换，比如[1,3], [2,4]可以换成[2,4],[1,3]
- 严格递增给的信息？直观相邻元素关系就行，可以递推去做
- 考虑到dp递推去做的时候，需要考虑哪些维度？一个是i，前i个元素的交换状态；另外需要扩充一个维度，表示i的位置换不换。
- 可以交换的情况有哪些？(1)a1<a2, b1<b2可以换0或者2次，（2）a1<b2, b1<a2, 可以换1次
- 两种可换的情况还需要特别考虑什么？可能都能满足，需要第二种可能时候取min
- 优化空间的算法是怎么优化？外侧定义f的时候i取两个维度就行，在每次遍历时候初始化一个局部的结果，利用(i-1)&1, i&1拿到索引prev和cur，处理完以后把局部结果赋值给f[cur], 最终的结果是f[(n-1)&1]