Đảo ngược toàn cục và cục bộ C++ (Global and Local Inversions)

Cho hoán vị A của [0..N-1]. Global inversion: i<j, A[i]>A[j]. Local inversion: i, A[i]>A[i+1]. Kiểm tra global == local.

Ví dụ

Input - [1,0,2] Output - true

Giải thích - Local: (1,0) tại i=0. Global: chỉ (1,0). Bằng nhau.

Phương pháp tiếp cận (Quan sát quan trọng)

Global = Local ⇔ Không có global inversion nào là non-local (khoảng cách ≥ 2). Tức là: ∀i, max(A[0..i]) ≤ A[i+2].

Ví dụ code C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        int maxVal = -1, n = A.size();
        for (int i = 0; i < n - 2; i++) {
            maxVal = max(maxVal, A[i]);
            if (maxVal > A[i + 2]) return false;
        }
        return true;
    }
};

int main() {
    vector<int> v = {1, 0, 2};
    Solution ob;
    cout << ob.isIdealPermutation(v);
    return 0;
}

Kết quả

1