801. Minimum Swaps To Make Sequences Increasing

解答思路

以上面表格的例子解釋:

如果min(A[i], B[i]) > max(A[i -1], B[i - 1])，
則A[i], B[i]無論有無swap都是正確的。
反之如果min(A[i], B[i]) <  max(A[i -1], B[i - 1])，那麼一定只有一種pattern
意及，min(A[i], B[i]) 與 min(A[i -1], B[i -1])要在同一列上；max(A[i], B[i]) 與 max(A[i -1], B[i -1])要在同一列上。

以上面的範例來說，一開始觀察min(A[1], B[1]) = 39 > max(A[0], B[0])；所以這裡的順序是無所謂的。我們前進到下一對。

min(A[2], B[2]) = 40 <= max(A[1], B[1])  = 41; 這裡便要求要一定的順序。
也就是min(A[2], B[2]) = 40和min(A[1], B[1]) = 39,
也就是max(A[2], B[2]) = 54和max(A[1], B[1]) = 41
需在同一列上。

同時，我們發現min(A[2], B[2]) = 40和min(A[1], B[1]) = 39並不在同一列上(同理，max(A[2], B[2]) = 54和max(A[1], B[1]) = 41不在同一列上)。

要達成這樣的目標有兩種方式；要嘛swap 41和39；要嘛swap 40和54，我們在這裡無法決定。
至少，我們已經知道在這個區間內有配對需要交換。

所以我們繼續下去， 一直到發現下一個邊界min(A[i], B[i]) > max(A[i -1], B[i - 1])為止。
我們可以從下圖看出這個區間的範圍。

注意到黃色區域的數字都是互相關聯的；也就是說，當我們固定了其中任何一組的順序，其他各組的順序也就定下來了；不然，會違反嚴格遞增的條件。

例如，當我們選定(63, 43)這組63在上面時，
我們就決定了下面的順序:

如橙色標明，需要5次交換。

反之，如果是下面的次序，需要4次交換(用綠色標明)。

因為4次比較少，所以我們選擇4次交換的方式。

執行過程即不斷的尋找區間，計算最好的交換次數。

時間複雜度為O(N)，空間複雜度為O(1) (原始版為O(N))。

上傳版本:

class Solution {
private:
    int calculate(vector<int>& A, vector<int>& B, int start, vector<int>& l) {
        int costA = 0, costB = 0;
        for (int k = 0; k < l.size(); k++) {
            if (l[k] != A[start + k]) {
                costA++;
            }
            if (l[k] != B[start + k]) {
                costB++;
            }
        }
        //printf("start = %d, range = %d cost A %d cost B %d\n", start, l.size(), costA, costB);
        return ((costA > costB) ? costB : costA);
    }
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        vector<int> lv; // large
        int min, max;
        bool minIsA, maxIsA;
        bool check = false;
        int start = 0;
        int total = 0;
        if (A[0] > B[0]) {
            lv.push_back(A[0]);
        } else {
            lv.push_back(B[0]);
        }  
        for (int i = 1; i < A.size(); i++) {
            if (A[i] > B[i]) {
                min = B[i];
                minIsA = false;
            } else {
                min = A[i];
                minIsA = true;
            }
            if (A[i - 1] > B[i - 1]) {
                max = A[i - 1];
                maxIsA = true;
            } else {
                max = B[i - 1];
                maxIsA = false;
            }
            if (min > max) { 
                // calculate
                if (check) {
                    total += calculate(A, B, start, lv);
                    check = false;
                }
                // cleanup
                lv.clear();
                start = i;
            } else { /*min <= max*/
                if (maxIsA == minIsA) { // violoation
                    check = true;
                }
            }
            if (A[i] > B[i]) {
                lv.push_back(A[i]);
            } else {
                lv.push_back(B[i]);
            }
        }
        if (check) {
            total += calculate(A, B, start, lv);
        }
        return total;
    }
};

優化版本:
1. costB就是l.size()減去costA
2. vector<int> lv可以省去。

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int total = 0;
        int prevMax = INT_MAX;
        int max, min;
        int top = 0;
        int range = 0;

        for (int i = 0; i < A.size(); i++) {
            min = (A[i] > B[i]) ? B[i] : A[i];
            if (prevMax < min) {
                if (top >= (range - top))
                    total += range - top;
                else 
                    total += top;
                range = top = 0;
            }
            if (A[i] > B[i]) {
                top++;
                prevMax = A[i];
            } else {
                prevMax = B[i];
            }
            range++;
        }
        total += (top >= (range - top)) ? (range - top) : top;
        return total;
    }
};