Partition Array into Disjoint Intervals ใน C++

คำอธิบายปัญหา

แบ่งอาร์เรย์ A เป็น left และ right ที่:

• ทุกค่าใน left <= ทุกค่าใน right
• left และ right ไม่ว่าง
• left มีขนาดน้อยที่สุด

ตัวอย่าง: [5,0,3,8,6] → 3 (left=[5,0,3], right=[8,6])

วิธีแก้ปัญหา

1. คำนวณ maxFromLeft[i] = max(A[0..i])
2. คำนวณ minFromRight[i] = min(A[i..n-1])
3. หา i น้อยที่สุดที่ minFromRight[i] >= maxFromLeft[i-1]

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        int n = A.size();
        vector<int> maxLeft(n);
        maxLeft[0] = A[0];
        for(int i = 1; i < n; i++) {
            maxLeft[i] = max(maxLeft[i-1], A[i]);
        }
        
        int minRight = A[n-1];
        int ans = n - 1;
        for(int i = n - 1; i >= 1; i--) {
            minRight = min(minRight, A[i]);
            if(minRight >= maxLeft[i-1]) {
                ans = i;
            }
        }
        return ans;
    }
};

int main() {
    vector<int> v1 = {5,0,3,8,6};
    Solution ob;
    cout << ob.partitionDisjoint(v1);
    return 0;
}

อินพุต

[5,0,3,8,6]

เอาต์พุต

3