企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文是「算法通关手册」题解库中对 LeetCode 0801「使序列递增的最小交换次数」（Minimum Swaps to Make Sequences Increasing）的完整讲解。题目标签为「数组、动态规划」，难度为困难，属于双数组线性动态规划的典型题目。读完本文，你将掌握如何用二维状态dp[i][j]刻画「第 i 位换 / 不换」两种决策，理解三种互斥情形下的状态转移方程，并能够独立写出时间 O(n)、空间 O(n)（可进一步压缩到 O(1)）的 Python 解法。

题目链接

• 0801. 使序列递增的最小交换次数 - 力扣

说明：本题解在手册中的收录位置见 题解目录 - 0800-0899，同时被归类于「数组、动态规划」分类下，具体条目可参考 分类题单 中「双串线性 DP 问题」一节。

题目大意

给定两个长度相等的整型数组A和B。允许交换两个数组相同位置上的元素（即把A[i]与B[i]互换），可以交换任意多个位置，但要求交换完成之后，数组A与数组B都保持严格递增。

要求：返回使数组A和B保持严格递增状态所需的最小交换次数。题目保证给定的输入一定有效（即一定存在至少一种合法交换方案）。

注意两个关键约束：

1. 交换只能发生在同一下标i的A[i]与B[i]之间，不能跨下标交换；
2. 要求的是「严格递增」，即A[i-1] < A[i]且B[i-1] < B[i]，相等的情况不满足要求。

示例演示

• 示例 1：
  • 输入：A = [1, 3, 5, 4]，B = [1, 2, 3, 7]
  • 输出：1
  • 解释：交换A[3]与B[3]（即4与7互换），得到A = [1, 3, 5, 7]、B = [1, 2, 3, 4]，两数组均严格递增，只需 1 次交换。

解题思路：二维状态动态规划

本题属于线性动态规划中的双串线性 DP。按照 08_03_linear_dp_01.md 中线性 DP 的划分方式，本题的输入是「两个数组」（双串），而每个下标位置只有「交换 / 不交换」两种离散决策，因此非常适合用带决策维度的二维状态来建模。

1. 状态定义

对于两个数组的每一个位置i，A[i]和B[i]只有两种情况：换或不换。

定义状态dp[i][j]：

• dp[i][0]：第i个位置的元素不交换（保持原样）时，前i + 1个位置所需的最小交换次数；
• dp[i][1]：第i个位置的元素交换（A[i]与B[i]互换）时，前i + 1个位置所需的最小交换次数。

2. 初始条件（边界）

当数组只有一个元素（size = 1）时，无论交换与否都能保证「严格递增」，所以：

• dp[0][0] = 0：第 0 个元素不做交换，交换次数为 0；
• dp[0][1] = 1：第 0 个元素做交换，交换次数为 1。

3. 状态转移：相邻位置的关系

如果有 2 个元素，为了保证两个数组中的相邻元素都严格递增，第 1 个元素是否交换与第 0 个元素直接相关；推广到多个元素时，第i个元素是否交换只与第i - 1个元素有关（马尔可夫式相邻依赖）。因此只需考察i与i - 1这两对相邻元素之间的关系。

先按「原本数组当前是否满足递增关系」划分为两大类：

情形 A：原本数组不满足递增关系

即A[i - 1] >= A[i]或B[i - 1] >= B[i]。

此时如果不做任何交换，两个数组在位置i处必然破坏严格递增，所以肯定要发生交换——问题只在于：交换第i位，还是交换第i - 1位？

• dp[i][0] = dp[i - 1][1]：第i位不交换，则第i - 1位必须交换；
• dp[i][1] = dp[i - 1][0] + 1：第i位交换，则第i - 1位不能交换（否则两数组会同时被「拆散」）。

情形 B：原本数组满足递增关系

即A[i - 1] < A[i]且B[i - 1] < B[i]。

此时原本已经满足递增，还需要进一步考察两个数组交叉方向上相邻元素的关系（因为一旦交换第i位，新的A[i]来自原B[i]，必须与新的B[i - 1]（可能来自原A[i - 1]或原B[i - 1]）保持严格递增）。这里再细分为两种情况：

• 情况 B1：交叉也满足递增，即A[i - 1] < B[i]且B[i - 1] < A[i]。 此时第i位交换与否，与第i - 1位交换与否互不影响，dp[i][j]直接取dp[i-1][j]两态中的较小值：

  • dp[i][0] = min(dp[i - 1][0], dp[i - 1][1])
  • dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1

• 情况 B2：交叉不满足递增，即A[i - 1] >= B[i]或B[i - 1] >= A[i]。 此时为了保证两个数组最终都严格递增，第i位与第i - 1位的交换决策必须保持一致：

  • dp[i][0] = dp[i - 1][0]：第i位不交换，则第i - 1位也不交换；
  • dp[i][1] = dp[i - 1][1] + 1：第i位交换，则第i - 1位也必须交换。

至此三种互斥情形全部覆盖，最终答案取最后一个位置两种状态下的较小值：

min(dp[size - 1][0], dp[size - 1][1])

4. 转移方程速查表

5. 解题代码（对应原题解实现）

class Solution: def minSwap(self, nums1: List[int], nums2: List[int]) -> int: size = len(nums1) dp = [[0 for _ in range(size)] for _ in range(size)] dp[0][1] = 1 for i in range(1, size): if nums1[i - 1] < nums1[i] and nums2[i - 1] < nums2[i]: if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]: # 第 i 位交换，与第 i - 1 位交换与否无关 dp[i][0] = min(dp[i-1][0], dp[i-1][1]) dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1 else: # 如果第 i 位不交换，则第 i - 1 位也不交换 # 如果第 i 位交换，则第 i - 1 位也必须交换 dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] + 1 else: dp[i][0] = dp[i - 1][1] # 如果第 i 位如果不交换，则第 i - 1 位必须交换 dp[i][1] = dp[i - 1][0] + 1 # 如果第 i 位交换，则第 i - 1 位不能交换 return min(dp[size - 1][0], dp[size - 1][1])

6. 复杂度分析

• 时间复杂度：O(n)。只需从第 1 位到第n - 1位遍历一次，每步做常数次比较与转移，总时间复杂度为O(n)，其中n为数组长度。
• 空间复杂度：O(n)。使用了一个n × 2的二维数组保存状态（本题解原实现中声明为size × size的矩阵，实际只使用了两列）。

从代码结构可以看出，每一步转移只依赖dp[i - 1][0]与dp[i - 1][1]两个值，因此可以推断空间可进一步优化：仅用两个变量keep（不交换）与swap（交换）滚动更新，即可把空间复杂度降为O(1)，这也是该题标准实现中最常用的写法。

7. 滚动数组优化版本（O(1) 空间）

class Solution: def minSwap(self, nums1: List[int], nums2: List[int]) -> int: keep = 0 # dp[i][0]：当前位不交换 swap = 1 # dp[i][1]：当前位交换 for i in range(1, len(nums1)): if nums1[i - 1] < nums1[i] and nums2[i - 1] < nums2[i]: if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]: keep, swap = min(keep, swap), min(keep, swap) + 1 else: keep, swap = keep, swap + 1 else: keep, swap = swap, keep + 1 return min(keep, swap)

该版本与二维数组版本转移逻辑完全等价，仅用两个变量代替整张表，适用于面试中进一步追问空间复杂度的场景。

举一反三：从本题看双串线性 DP 的建模套路

本题在「算法通关手册」的线性动态规划体系中属于双串输入、带决策维度的典型题目。与单串线性 DP（如最长递增子序列中dp[i]表示以nums[i]结尾的解）相比，本题的核心差异在于：

1. 决策离散且互斥：每个位置只有「换 / 不换」两种选择，因此状态天然拆成两维（j = 0 / 1）；
2. 相邻依赖（局部性）：第i位的决策只影响且只受第i - 1位影响，不需要枚举前面的所有位置，这是本题能做到O(n)的关键；
3. 交叉约束：双数组问题必须同时检查「同向递增」与「交叉递增」两组条件，缺一不可，这也是本题容易写错的地方。

建议读者在完成本题后，回顾 动态规划基础 与 线性 DP 系列 章节，将「决策维度状态」的思想与「买卖股票」系列（同样使用dp[i][0/1]表示持股 / 空仓）等题目对照学习，可以更深刻地理解二维状态线性 DP 的通用模式。

总结

LeetCode 0801「使序列递增的最小交换次数」是一道质量很高的困难级动态规划题，其核心价值在于：

• 用dp[i][j]把「是否交换」这一离散决策编码进状态；
• 通过分析相邻位置的三类关系（不满足递增 / 交叉满足递增 / 交叉不满足递增）推导出完备的状态转移方程；
• 在保证O(n)时间复杂度的同时，可进一步把空间压缩到O(1)。

掌握本题的建模思路后，你不仅能独立解决这道困难题，还能将其推广到其他「相邻约束 + 二元决策」类的双数组问题上。题解原始文档见 docs/solutions/0800-0899/minimum-swaps-to-make-sequences-increasing.md，更多动态规划专题可参考 08_dynamic_programming 章节。

• 教程
• 文档
• 知识库