LeetCode 801. 使序列递增的最小交换次数
题目描述
题意分析
每次只能交换两个等长数组在同一下标处的两个数，求让两条序列都严格递增的最少交换次数。每个位置只需决定交换或不交换，不能移动下标；题目保证存在合法方案。
解法：动态规划（keep / swap）
核心思路
[!blue]
严格递增只需每对相邻位置都满足大小关系。当前能否接在此前合法前缀后面，只取决于前一位置是否交换，不必记录更早的具体选择。因此维护两个最优状态：
keep是前缀已合法且末位未交换的最少次数，swap是前缀已合法且末位交换的最少次数。处理下标
i时，先保留旧状态，再计算newKeep、newSwap。若原方向满足nums1[i] > nums1[i-1]且nums2[i] > nums2[i-1]，前后可以都不交换，也可以都交换，对应候选为newKeep = keep、newSwap = swap + 1。若交叉方向满足
nums1[i] > nums2[i-1]且nums2[i] > nums1[i-1]，前后可以采用相反状态，对应候选为newKeep = swap、newSwap = keep + 1。两种条件可能同时成立，需要分别尝试并取最小值，不能使用else if。只有当前选择交换时才增加一次费用。这四种转移覆盖了前后两位的所有交换组合；此前相同末位状态只保留最少次数，不会影响后续可行性，所以逐位取最小值能得到全局最优。首位不受相邻限制，初始化
keep = 0、swap = 1，最终末位状态不限，返回两者最小值。题目保证完整方案存在，所以每个前缀也可行。将某个可行前缀的所有交换选择取反，只会把两条递增序列整体对调，因此相反的末位状态也可行。两种旧状态始终都是有限值；新状态先置为无穷大只是为了方便取最小值，转移完成后再统一覆盖旧状态。
解题步骤
- 初始化首位不交换的代价为零、交换为一。
- 每一轮创建两个新的不可达代价，保留上一轮状态。
- 按原方向和交叉方向分别更新当前两种状态。
- 用新状态替换旧状态，最终返回两者较小值。
代码实现
class Solution {
public int minSwap(int[] nums1, int[] nums2) {
int n = nums1.length;
int keep = 0;
// 首位选择交换也需一次操作，不交换的初始代价才是零。
int swap = 1;
for (int i = 1; i < n; i++) {
int newKeep = Integer.MAX_VALUE;
int newSwap = Integer.MAX_VALUE;
// 原方向递增时，相邻位置可以保持相同交换状态。
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
newKeep = Math.min(newKeep, keep);
newSwap = Math.min(newSwap, swap + 1);
}
// 交叉方向递增时，相邻位置可以采用相反交换状态。
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
newKeep = Math.min(newKeep, swap);
newSwap = Math.min(newSwap, keep + 1);
}
// 两类转移都完成后再覆盖旧值，避免读取本轮结果。
keep = newKeep;
swap = newSwap;
}
return Math.min(keep, swap);
}
}
func minSwap(nums1 []int, nums2 []int) int {
n := len(nums1)
keep := 0
// 首位选择交换也需一次操作，不交换的初始代价才是零。
swap := 1
for i := 1; i < n; i++ {
newKeep := 1 << 30
newSwap := 1 << 30
// 原方向递增时，相邻位置可以保持相同交换状态。
if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] {
if keep < newKeep {
newKeep = keep
}
if swap+1 < newSwap {
newSwap = swap + 1
}
}
// 交叉方向递增时，相邻位置可以采用相反交换状态。
if nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1] {
if swap < newKeep {
newKeep = swap
}
if keep+1 < newSwap {
newSwap = keep + 1
}
}
// 两类转移都完成后再覆盖旧值，避免读取本轮结果。
keep = newKeep
swap = newSwap
}
if keep < swap {
return keep
}
return swap
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$，滚动维护两个状态。
关键点总结
[!green]
- 交换成本只在当前选择交换时增加一。
- 两组条件需要独立判断，不能写成互斥分支。
- 转移读取的全部是上一位置的状态。
易错点总结
[!yellow]
- 首位交换代价初始化为零：会漏算第一位发生的交换。
- 使用大于等于代替严格大于：会接受相邻元素相等的非法序列。
- 用 else if 处理交叉条件：两种条件同时满足时可能漏掉更优转移。
- 原地覆盖 keep 后再用它更新 swap：混淆前一位置与当前位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1187. 使数组严格递增 | 困难 | 同样用DP最少修改操作使序列递增，原题替换一个数组中的元素，本题只允许交换同下标两项并要求两串都递增。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！