线性动态规划：使序列严格递增的最小交换次数 题目描述 给定两个长度相等的整数数组 nums1 和 nums2 ，每次操作可以交换两个数组中 相同索引 位置的元素。要求通过若干次操作后，两个数组都变成 严格递增 的数组。请计算并返回使两个数组严格递增所需的最小交换次数。如果无法实现，则返回 -1。 示例 输入：nums1 = [ 1,3,5,4], nums2 = [ 1,2,3,7 ] 输出：1 解释：交换索引 3 的位置（即交换 nums1[ 3] 和 nums2[ 3]），得到 nums1 = [ 1,3,5,7]，nums2 = [ 1,2,3,4 ]，两个数组均严格递增。 解题过程 步骤1：问题分析 每个索引 i 有两种状态： 不交换 ：保留 nums1[i] 和 nums2[i] 在原数组。 交换 ：将 nums1[i] 和 nums2[i] 互换。 目标：确保每个数组的每个位置满足严格递增（即 nums1[i] < nums1[i+1] 且 nums2[i] < nums2[i+1] ）。 约束：交换操作仅限同一索引，因此每个位置的状态会影响后续决策。 步骤2：定义状态 定义动态规划数组： keep[i] ：使前 i+1 个位置满足严格递增，且 第 i 位不交换 的最小交换次数。 swap[i] ：使前 i+1 个位置满足严格递增，且 第 i 位交换 的最小交换次数。 步骤3：初始条件 对于索引 0（第一个位置）： keep[0] = 0 （不交换，成本为 0）。 swap[0] = 1 （交换，成本为 1）。 步骤4：状态转移方程 对于每个位置 i （从 1 开始），考虑前一个位置 i-1 的状态与当前位的值关系： 情况1：i-1 和 i 均不交换 需满足： nums1[i-1] < nums1[i] 且 nums2[i-1] < nums2[i] 若满足，则 keep[i] = min(keep[i], keep[i-1]) 。 情况2：i-1 交换，i 不交换 需满足： nums2[i-1] < nums1[i] 且 nums1[i-1] < nums2[i] 若满足，则 keep[i] = min(keep[i], swap[i-1]) 。 情况3：i-1 不交换，i 交换 需满足： nums1[i-1] < nums2[i] 且 nums2[i-1] < nums1[i] 若满足，则 swap[i] = min(swap[i], keep[i-1] + 1) 。 情况4：i-1 和 i 均交换 需满足： nums2[i-1] < nums2[i] 且 nums1[i-1] < nums1[i] 若满足，则 swap[i] = min(swap[i], swap[i-1] + 1) 。 步骤5：处理无法满足条件的情况 若某个位置 i 的 keep[i] 和 swap[i] 均为无穷大，说明无法使序列严格递增，返回 -1。 步骤6：最终结果 返回 min(keep[n-1], swap[n-1]) ，其中 n 为数组长度。 举例验证 以示例 nums1 = [1,3,5,4] , nums2 = [1,2,3,7] 为例： i=0 ： keep[0]=0 , swap[0]=1 。 i=1 ： 情况1（均不交换）： 3>1 且 2>1 ✅ → keep[1]=0 。 情况2（前换后不换）： 2<3 ✅ 且 1<2 ✅ → keep[1]=min(0,1)=0 。 情况3（前不换后换）： 1<2 ✅ 且 1<3 ✅ → swap[1]=0+1=1 。 情况4（均交换）： 2<3 ✅ 且 1<2 ✅ → swap[1]=min(1,1+1)=1 。 i=2 ： 情况1： 5>3 ✅ 且 3>2 ✅ → keep[2]=0 。 情况2： 3<5 ✅ 且 2<3 ✅ → keep[2]=min(0,1)=0 。 情况3： 3<3 ❌（不满足严格递增）→ 跳过。 情况4： 3<5 ✅ 且 2<3 ✅ → swap[2]=1+1=2 。 i=3 ： 情况1： 4<5 ❌ → 跳过。 情况2： 3<4 ✅ 且 5<7 ✅ → keep[3]=0+1=1 。 情况3： 5<7 ✅ 且 3<4 ✅ → swap[3]=0+1=1 。 情况4： 3<4 ✅ 且 5<7 ✅ → swap[3]=min(1,2+1)=1 。 结果： min(keep[3], swap[3]) = min(1,1) = 1 。 总结 本题通过维护两个状态（交换/不交换）的DP数组，逐步验证相邻位置的严格递增条件，确保状态转移的合法性。时间复杂度 O(n)，空间复杂度可优化至 O(1)。