思路 遍历数组。维持一个max,表示当前数组应维持的最小的i,如果arr[i]大于max,就更新max为arr[i],然后如果i==max,也就说i已经到达最小要求,就cnt++,且max更新为数组下一个位置的值。
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
if (arr.size() == 1)
return 1;
int max = -1;
int cnt = 0;
for (int i = 0; i < arr.size(); i++) {
if (max == -1) {
max = arr[i];
}
if (arr[i] > max)
max = arr[i];
if (i == max) {
cnt++;
max = arr[i + 1];
}
//cout << i << "," << max << endl;
}
return cnt;
}
};