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

### 题目地址(801. 使序列递增的最小交换次数)

<https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing/>

### 题目描述

```
我们有两个长度相等且不为空的整型数组 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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/d35xen.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/801.minimum-swaps-to-make-sequences-increasing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.