线性动态规划：使序列递增的最小交换次数

题目描述
给定两个长度相等的整数数组 nums1 和 nums2。在一次操作中，你可以交换 nums1 和 nums2 在相同位置上的元素。也就是说，交换 nums1[i] 和 nums2[i]。你需要找出使得 nums1 和 nums2 都成为严格递增数组所需的最小交换次数。题目保证输入总是有效的，即存在一种交换方式使得两个数组都严格递增。

示例
输入：nums1 = [1,3,5,4], nums2 = [1,2,3,7]
输出：1
解释：交换 nums1[3] 和 nums2[3] 后，两个数组变为 [1,3,5,7] 和 [1,2,3,4]，都是严格递增的。

解题过程

这个问题要求我们通过最少的交换操作，使得两个数组在对应位置交换后，各自都是严格递增的。关键在于每个位置有两种状态：交换或不交换。我们可以使用动态规划来记录到达每个位置时，在该位置交换或不交换的情况下，所需的最小交换次数。

1. 定义状态
   我们定义两个一维数组（或两个变量，因为每个状态只依赖于前一个状态）来记录状态：

   • keep[i]：表示不交换位置 i 的元素时，使得从位置 0 到位置 i 的两个数组都满足严格递增条件所需的最小交换次数。
   • swap[i]：表示交换位置 i 的元素时，使得从位置 0 到位置 i 的两个数组都满足严格递增条件所需的最小交换次数。

2. 寻找状态转移方程
   我们需要考虑位置 i 和位置 i-1 之间的关系。对于位置 i 的决策（交换或不交换），它必须与位置 i-1 的决策（交换或不交换）相容，以确保从 i-1 到 i 的递增性。

   我们检查以下两个条件：

   • 条件A（自然递增）：nums1[i-1] < nums1[i] 且 nums2[i-1] < nums2[i]。如果这个条件满足，意味着如果 i-1 位置没有交换，那么 i 位置也可以不交换；如果 i-1 位置交换了，那么 i 位置也可以交换（因为交换是同步的，交换后 nums1 和 nums2 在 i-1 和 i 的相对大小关系与交换前一致）。
   • 条件B（交叉递增）：nums1[i-1] < nums2[i] 且 nums2[i-1] < nums1[i]。如果这个条件满足，意味着如果 i-1 位置没有交换，那么 i 位置需要交换；如果 i-1 位置交换了，那么 i 位置可以不交换（因为交换 i-1 后，原来的 nums2[i-1] 变成了 nums1[i-1]，需要小于 nums1[i]；原来的 nums1[i-1] 变成了 nums2[i-1]，需要小于 nums2[i]）。

   根据这两个条件的组合，我们可以写出状态转移方程：

   • 如果条件A满足：
     • keep[i] 可以从 keep[i-1] 转移而来（i-1 不交换，i 也不交换）。
     • swap[i] 可以从 swap[i-1] + 1 转移而来（i-1 交换了，i 也交换，所以交换次数加1）。
   • 如果条件B满足：
     • keep[i] 可以从 swap[i-1] 转移而来（i-1 交换了，i 不交换）。
     • swap[i] 可以从 keep[i-1] + 1 转移而来（i-1 不交换，i 交换，所以交换次数加1）。

   在实际计算中，如果两个条件都满足，那么 keep[i] 和 swap[i] 应该取所有可能转移来源中的最小值。

   因此，完整的转移方程是：

   keep[i] = 一个很大的数（表示不可达）
   swap[i] = 一个很大的数
   
   if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) {
       keep[i] = min(keep[i], keep[i-1])
       swap[i] = min(swap[i], swap[i-1] + 1)
   }
   if (nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i]) {
       keep[i] = min(keep[i], swap[i-1])
       swap[i] = min(swap[i], keep[i-1] + 1)
   }
   

3. 初始化
   对于第一个位置（i = 0）：

   • keep[0] = 0：第一个位置不交换，交换次数为0。
   • swap[0] = 1：第一个位置交换，交换次数为1。

4. 计算顺序
   从 i = 1 开始，遍历到数组的最后一个位置。

5. 最终结果
   最终结果是 min(keep[n-1], swap[n-1])，其中 n 是数组的长度。

6. 复杂度分析

   • 时间复杂度：O(n)，只需要遍历数组一次。
   • 空间复杂度：如果使用两个数组 keep 和 swap，则是 O(n)。但我们可以发现，每个状态 i 只依赖于状态 i-1，因此可以使用两个变量来滚动计算，将空间复杂度优化到 O(1)。

举例说明

以示例 nums1 = [1,3,5,4], nums2 = [1,2,3,7] 为例：

• i = 0:

  • keep_prev = 0
  • swap_prev = 1

• i = 1 (比较位置0和位置1):

  • 条件A: nums1[0] (1) < nums1[1] (3) 且 nums2[0] (1) < nums2[1] (2) -> 满足。
  • 条件B: nums1[0] (1) < nums2[1] (2) 且 nums2[0] (1) < nums1[1] (3) -> 满足。
  • keep_curr:
    • 来自条件A: keep_prev = 0
    • 来自条件B: swap_prev = 1
    • min(0, 1) = 0
  • swap_curr:
    • 来自条件A: swap_prev + 1 = 1 + 1 = 2
    • 来自条件B: keep_prev + 1 = 0 + 1 = 1
    • min(2, 1) = 1
  • 更新: keep_prev = 0, swap_prev = 1

• i = 2 (比较位置1和位置2):

  • 条件A: nums1[1] (3) < nums1[2] (5) 且 nums2[1] (2) < nums2[2] (3) -> 满足。
  • 条件B: nums1[1] (3) < nums2[2] (3)? 不满足 (3 < 3 不成立)。
  • keep_curr:
    • 来自条件A: keep_prev = 0
  • swap_curr:
    • 来自条件A: swap_prev + 1 = 1 + 1 = 2
  • 更新: keep_prev = 0, swap_prev = 2

• i = 3 (比较位置2和位置3):

  • 条件A: nums1[2] (5) < nums1[3] (4)? 不满足。
  • 条件B: nums1[2] (5) < nums2[3] (7) 且 nums2[2] (3) < nums1[3] (4) -> 满足。
  • keep_curr:
    • 来自条件B: swap_prev = 2
  • swap_curr:
    • 来自条件B: keep_prev + 1 = 0 + 1 = 1
  • 更新: keep_prev = 2, swap_prev = 1

• 最终结果: min(keep_prev, swap_prev) = min(2, 1) = 1

结果正确，最小交换次数为1。