Description Link to heading

768.max-chunks-to-make-sorted-ii

Solution Link to heading

A sufficient condition for an array to be divisible into blocks that satisfy the condition is that all elements in the block are less than or equal to any of the undivided elements in the right-hand array.

Code Link to heading 

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int idx = 0; // 表示划分arr
        int ans = 0;
        map<int, int, std::greater<int>> l_map;
        map<int, int> r_map;
        for (int i = 0; i < arr.size(); i++)
            r_map[arr[i]]++;
        while (idx < arr.size()) {
            for (int i = idx; i < arr.size(); i++) {
                l_map[arr[i]]++;
                r_map[arr[i]]--;
                if (r_map[arr[i]] == 0)
                    r_map.erase(arr[i]);
                if (r_map.empty()) 
                    break;
                if (l_map.begin()->first <= r_map.begin()->first) {
                    idx = i + 1;
                    ans++;
                    break;
                }
            }
            if (r_map.empty()) {
                ans++;
                break;
            }
        }
        return ans;
    }
};