801. Minimum Swaps To Make Sequences Increasing

思路比较直接，关键是分析清楚
其实是有三种情况
A[i - 1]   A[i]
B[i - 1]    B[i]

1.先看看是不是可以不swap保持valid

A[i] > A[i - 1] && B[i] > B[i - 1]

2.试试是不是可以swap

32.41 %
class Solution {
    public int minSwap(int[] A, int[] B) {
        int len = A.length;
        int[] swap = new int[len]; // min if we swap A[i]
        int[] noSwap = new int[len]; // min if we don't swap A[i]
        Arrays.fill(swap, Integer.MAX_VALUE);
        Arrays.fill(noSwap, Integer.MAX_VALUE);
        swap[0] = 1;
        noSwap[0] = 0;
        // A[i - 1]  A[i]
        // B[i - 1]  A[i]
       
        for (int i = 1; i < len; i++) {
            if (A[i] > A[i - 1] && B[i] > B[i - 1]){ // good case, no need to swap
                swap[i] = swap[i - 1] + 1;
                noSwap[i] = noSwap[i - 1];
            }
            if (A[i] > B[i - 1] && B[i] > A[i - 1]) { // we can swap
                swap[i] = Math.min(swap[i], noSwap[i - 1] + 1);
                noSwap[i] = Math.min(noSwap[i], swap[i - 1]);
            }
        }
        return Math.min(swap[len - 1], noSwap[len - 1]);
    }
}


[0,3,5,8,9] [2,1,4,6,9]
[0,4,4,5,9] [0,1,6,8,10]
[0,7,8,10,10,11,12,13,19,18] [4,4,5,7,11,14,15,16,17,20]