Max Chunks To Make Sorted ใน C++

โจทย์: Max Chunks To Make Sorted

ให้อาร์เรย์ arr ที่เป็นการจัดเรียง (permutation) ของ [0, 1, ..., arr.length - 1] เราต้องแบ่งอาร์เรย์ออกเป็นจำนวน "chunks" (ส่วนนิ่ง) บางจำนวน แล้วเรียงลำดับแต่ละ chunk แยกกัน หลังจากต่อชิ้นส่วนเข้าด้วยกัน ผลลัพธ์ต้องเป็นอาร์เรย์ที่เรียงลำดับจากน้อยไปมาก

เป้าหมาย: หา จำนวน chunks สูงสุด ที่ทำได้

ตัวอย่าง: arr = [1,0,2,3,4] → สามารถแบ่งได้ 4 chunks: [1,0], [2], [3], [4] (เรียง chunk แรกได้ [0,1] แล้วต่อกันได้ [0,1,2,3,4])

อัลกอริทึม

1. กำหนด ans = 0, maxVal = INT_MIN, n = arr.size()
2. วนลูป i จาก 0 ถึง n-1:
   • อัปเดต maxVal = max(maxVal, arr[i])
   • หาก maxVal == i ให้เพิ่ม ans++ (เพราะองค์ประกอบ 0 ถึง i ครบทุกตัวแล้ว สามารถตัด chunk ได้)
3. ส่งคืน ans

เหตุผล: เนื่องจากอาร์เรย์เป็น permutation ของ 0 ถึง n-1 หากค่าสูงสุดที่เจอจนถึง index i เท่ากับ i แสดงว่าองค์ประกอบ 0..i ครบทุกตัวอยู่ในช่วง 0..i แล้ว จึงสามารถตัด chunk ที่นั่นได้

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

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

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = 0;
        int maxVal = INT_MIN;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            maxVal = max(maxVal, arr[i]);
            if (maxVal == i) {
                ans++;
            }
        }
        return ans;
    }
};

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

Input

[1,0,2,3,4]

Output

4

ความซับซ้อน (Complexity)

• เวลา: O(n) - วนลูปผ่านอาร์เรย์ 1 ครั้ง
• พื้นที่: O(1) - ใช้ตัวแปรคงที่