题目

769. 最多能完成排序的块

思路

数组是0-n排列，那么对于0-i的元素中最大值不小于i，即max(arr[0-i])>=i；如：数组为0-5的排列，则0-3的下标元素中最大的值不小于3。

那么如果0-i中有大于i的元素，必定i+1-n中有小于i的元素，那么这个i就不能作为划分的界限，因为0~i与i+1~n排好序后，前者中大于后者的数。

因此，只有max(arr[0~i])==i，这个i才能够作为界限。

    public int maxChunksToSorted(int[] arr) {
        int counts = 0;//记录分割成了几组
        int max = 0;//记录0-i中数组最大的值
        //遍历数组
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);//找到0-i中最大的元素
            if (max == i) { //找到界限
                counts++;
            }
        }
        return counts;
    }