# 0801. 使序列递增的最小交换次数
### 题目地址(801. 使序列递增的最小交换次数)
### 题目描述
```
我们有两个长度相等且不为空的整型数组 A 和 B 。
我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。
给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
示例:
输入: A = [1,3,5,4], B = [1,2,3,7]
输出: 1
解释:
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。
注意:
A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
A[i], B[i] 均为 [0, 2000]区间内的整数。
```
### 前置知识
* 动态规划
### 公司
* 暂无
### 思路
要想解决这道题，需要搞定两个关键点。
#### 关键点一：无需考虑全部整体，而只需要考虑相邻两个数字即可
这其实也是可以使用动态规划解决问题的关键条件。对于这道题来说，**最小**的子问题就是当前项和前一项组成的局部，**无法**再小了，**没有必要**再大了。
为什么只关心两个数字即可？因为要使得整个数组递增，**假设**前面的 i - 2 项已经满足递增了，那么现在**采取某种方式**使得满足 A\[i] > A\[i-1] 即可(B 也是同理)。
> 因为 A\[i - 1] > A\[i-2] 已经成立，因此如果 A\[i] > A\[i - 1]，那么整体就递增了。
这提示我们可以使用动态规划来完成。 如果上面的这些没有听懂，则很有可能对动态规划不熟悉，建议先看下基础知识。
#### 关键点二：相邻两个数字的大小关系有哪些？
由于题目一定有解，因此交换相邻项中的**一个或两个**一定能满足**两个数组都递增**的条件。换句话说，如下的情况是不可能存在的：
```
A:[1,2,4]
B:[1,5,1]
```
因为无论怎么交换都无法得到两个递增的序列。那相邻数字的大小关系究竟有哪些呢？实际上大小关系一共有四种。为了描述方便，先列举两个条件，之后直接用 q1 和 q2 来引用这两个关系。
```
q1：A[i-1] < A[i] and B[i-1] < B[i]
q2：A[i-1] < B[i] and B[i-1] < A[i]
```
* q1 表示的是两个数组本身就已经递增了，你**可以选择**不交换。
* q2 表示的是两个数组必须进行一次交换，你**可以选择**交换 i 或者交换 i - 1。
铺垫已经有了，接下来我们来看下这四种关系。
关系一：q1 满足 q2 满足。换不换都行，换 i 或者 i - 1 都行, 也可以都换
关系二：q1 不满足 q2 不满足。无解，对应上面我举的不可能存在的情况
关系三：q1 满足 q2 不满足。换不换都行，但是如果换需要都换。
关系四：q1 不满足 q2 满足 。必须换，换 i 或者 i - 1
接下来按照上面的四种关系进行模拟即可解决。
### 关键点
* 无需考虑全部整体，而只需要考虑相邻两个数字即可
* 分情况讨论
* 从题目的**一定有解**条件入手
### 代码
* 语言支持：Python3
Python3 Code:
```py
class Solution:
def minSwap(self, A: List[int], B: List[int]) -> int:
n = len(A)
swap = [n] * n
no_swap = [n] * n
swap[0] = 1
no_swap[0] = 0
for i in range(1, len(A)):
q1 = A[i-1] < A[i] and B[i-1] < B[i]
q2 = A[i-1] < B[i] and B[i-1] < A[i]
if q1 and q2:
no_swap[i] = min(swap[i-1], no_swap[i-1]) # 都不换或者换i-1
swap[i] = min(swap[i-1], no_swap[i-1]) + 1 # 都换 或者 换 i
if q1 and not q2:
swap[i] = swap[i-1] + 1 # 都换
no_swap[i] = no_swap[i-1] # 都不换
if not q1 and q2:
swap[i] = no_swap[i-1] + 1 # 换 i
no_swap[i] = swap[i-1] # 换 i - 1
return min(swap[n-1], no_swap[n-1])
```
实际上，我们也可以将逻辑进行合并，这样代码更加简洁。力扣中国题解区很多都是这种写法。即：
```py
if q1:
no_swap[i] = no_swap[i-1] # 都不换
swap[i] = swap[i-1] + 1 # 都换
if q2:
swap[i] = min(swap[i], no_swap[i-1] + 1) # 换 i
no_swap[i] = min(no_swap[i], swap[i-1]) # 换 i - 1
```
可以看出，这种写法和上面逻辑是一致的。
逻辑合并之后的代码，更简短。但由于两个分支可能都执行到，因此不太容易直接写出。
代码：
```py
class Solution:
def minSwap(self, A: List[int], B: List[int]) -> int:
n = len(A)
swap = [n] * n
no_swap = [n] * n
swap[0] = 1
no_swap[0] = 0
for i in range(1, len(A)):
# 如果交换之前有序，则可以不交换
if A[i-1] < A[i] and B[i-1] < B[i]:
no_swap[i] = no_swap[i-1]
swap[i] = swap[i-1] + 1
# 否则至少需要交换一次（交换当前项或者前一项）
if A[i-1] < B[i] and B[i-1] < A[i]:
swap[i] = min(swap[i], no_swap[i-1] + 1) # i 换
no_swap[i] = min(no_swap[i], swap[i-1]) # i - 1 换
return min(swap[n-1], no_swap[n-1])
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
