LC.P769[最多能完成排序的块]

方法一：贪心

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int ans = 0, max = -1;
        for (int i = 0; i < arr.length; ++i) {
            max = Math.max(max, arr[i]);
            if (max == i) ++ans;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$