LeetCode769. 最多能完成排序的块

题目

数组

arr

是

[0, 1, ..., arr.length - 1]

的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
      

示例 2:

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
      

注意:

• arr

  的长度在

  [1, 10]

  之间。

• arr[i]

  是

  [0, 1, ..., arr.length - 1]

  的一种排列。

分析

解题报告链接 点击打开链接

维护一个右边最小数数组 和 左边最大数， 本题的排序方式简单来说就是  左边块里的最大数 小于 右边块里的最小数，

首先就先从后向前找出从当前位置i到结束arr.length的最小数，

然后从前向后遍历数组，维护一个左边最大数，当左边最大数小于或等于右边最小数时，count+1，

记得更新一下左边最大数的数值。

代码

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int len = arr.length;
        int count = 1;

        int leftMax = arr[0];
        int[] rightMin = new int[len];
        rightMin[len-1] = arr[len-1];

        for (int i = len - 2; i >= 0 ; i--) {
            rightMin[i] = Math.min(arr[i],rightMin[i+1]);
        }

        for (int i = 1; i < len; i++) {
            if (rightMin[i] >= leftMax){
                count++;
                leftMax = arr[i];
            }else {
                leftMax = Math.max(arr[i] , leftMax);
            }
        }


        return count;
    }
}