768.max-chunks-to-make-sorted-ii 最多能完成排序的块II

问题描述

768.最多能完成排序的块II

解题思路

可以划分成满足条件的块的充分必要条件是，块内所有元素都小于等于右侧数组中未划分的任一元素。

本题中使用了map来进行处理，实际上使用单调栈就可以了。

代码

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;
    }
};