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

Question

我们有两个长度相等且不为空的整型数组 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:

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])

实际上，我们也可以将逻辑进行合并，这样代码更加简洁。力扣中国题解区很多都是这种写法。即：

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

可以看出，这种写法和上面逻辑是一致的。

逻辑合并之后的代码，更简短。但由于两个分支可能都执行到，因此不太容易直接写出。

代码：

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)$