Global and Local Inversions: การผกผันส่วนกลางและส่วนท้องถิ่นใน C++

ปัญหา

Permutation A ของ [0, 1, ..., N-1]

• Global Inversions: คู่ (i,j) ที่ i < j และ A[i] > A[j]
• Local Inversions: คู่ (i, i+1) ที่ A[i] > A[i+1]

ทุก Local Inversion เป็น Global Inversion หาเงื่อนไขที่ Global = Local (คือ ไม่มี Global Inversion ที่ไม่ใช่ Local)

ตัวอย่าง: [1,0,2] → Local: (1,0) 1 คู่, Global: (1,0) 1 คู่ → True

ข้อสังเกตสำคัญ

Global = Local ⟺ ไม่มี Non-local Inversion ⟺ ไม่มี i, j ที่ j ≥ i+2 และ A[i] > A[j]

คือ ทุก Element ต้องไม่ได้เคลื่อนที่ห่างจากตำแหน่งเดิมเกิน 1 ที่

|A[i] - i| ≤ 1 สำหรับทุก i

อัลกอริทึม O(N)

maxVal = -1
for i = 0 to n-3:
    maxVal = max(maxVal, A[i])
    if maxVal > A[i+2]: return false
return true

ตรวจสอบว่า Max ของ Prefix (ถึง i) ไม่เกิน A[i+2] (Element ที่ห่าง 2 ที่)

โค้ด C++

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

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        int maxVal = -1;
        int 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() {
    Solution ob;
    vector<int> v = {1, 0, 2};
    cout << ob.isIdealPermutation(v);  // 1 (true)
    return 0;
}

ตัวอย่างที่เป็น False

[2, 0, 1]  // 2 อยู่ index 0 แต่ควรอยู่ index 2 (เคลื่อนที่ 2 ที่)
i=0: maxVal=2, A[2]=1 → 2 > 1 → False
Global: (2,0), (2,1) = 2 pairs
Local: (2,0) = 1 pair

ความซับซ้อน

• Time: O(n)
• Space: O(1)

Input / Output

Input:  [1,0,2]
Output: 1 (true)