acytoo

Leetcode 801 Minimum Swaps to Make Sequences Increasing

看到题，首先判断题目类型，是一道什么题。常见的题型有DFS, BFS, DP, Greedy, Math, Recursion等。分析这道题使用DFS， DP的可能性较大。

DP题目，难点是状态转移方程。如果能够弄清楚要记录的状态以及转移原则，DP就很简单了。

这道题需要记录的状态有两个：

  1. 交换A[i], B[i]，使两个从0到当前索引i的子序列A[0:i], B[0:i]单调递增的，最小交换次数swap。
  2. 不交换A[i], B[i]，使两个从0到当前索引i的子序列A[0:i], B[0:i]单调递增的，最小交换次数keep。

有了状态，我们考虑状态转移问题。当序列中只有一个数字的时候，是严格单调递增的，这时swap[0] = 1, keep[0] = 0，我们从索引为1的数字开始。如果当前A[i], B[i]使两个序列都是递增的，不需要交换，keep[i] = keep[i-1]，对于swap而言，就是swap[i] = swap[i-1] + 1，因为swap[i]记录的是交换数字A[i]，B[i]使两个子序列严格单调递增的交换次数，所以我们除了交换索引i上的数字，还要交换前面的数字（极端情况是交换两个序列）；如果当前数字使某个序列不再递增了，那么有两种可能的操作：1.交换当前数字保留前一组数字：swap[i] = keep[i-1] + 1，2.保留当前数字交换前一组数字keep[i] = swap[i-1]。注意，即使当前数字使两个序列都递增，如果交换后仍能保持递增，那么也是可以交换的，所以两个if是并列的，并不是if-else的形式。

完整代码如下

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
 public:
  int minSwap(vector<int>& A, vector<int>& B) {
    const int n = A.size();
    vector<int> keep (n, INT_MAX), swap (n, INT_MAX);

    keep[0] = 0;
    swap[0] = 1;

    for (int i=1; i<n; ++i) {
      int j = i - 1;
      if (A[i] > A[j] && B[i] > B[j]) {
        keep[i] = keep[j];
        swap[i] = swap[j] + 1;
      }
      if (B[i] > A[j] && A[i] > B[j]) {
        swap[i] = min(swap[i], keep[j] + 1);
        keep[i] = min(keep[i], swap[j]);
      }
    }
    return min(swap.back(), keep.back());
  }
};

同大多数DP题目一样，我们可以只保留前一位状态来转移，使空间复杂度从 $\mathcal{O}(n)$ 减小到 $\mathcal{O}(1)$，代码如下。

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
 public:
  int minSwap(vector<int>& A, vector<int>& B) {
    int k1 = 0, s1 = 1;
    for (int i=1, n=A.size(); i<n; ++i) {
      int j = i - 1, k2 = INT_MAX, s2 = INT_MAX;
      if (A[i] > A[j] && B[i] > B[j]) {
        k2 = k1;
        s2 = s1 + 1;
      }
      if (B[i] > A[j] && A[i] > B[j]) {
        s2 = min(s1, k1 + 1);
        k2 = min(k2, s1);
      }
      s1 = s2; k1 = k2;
    }
    return min(s1, k1);
  }
};
#直达链接

LeetCode 801. Minimum Swaps To Make Sequences Increasing

相关文章：