问题描述
解题思路
可以划分成满足条件的块的充分必要条件是，块内所有元素都小于等于右侧数组中未划分的任一元素。
本题中使用了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;
}
};