768. Max Chunks To Make Sorted I

题目大意：给一个排列，可能有重复元素，我们将数组拆分成一些“块”（分区），并对每个块进行单独排序。连接它们之后，结果等于排序后的数组。问最多能够分成多少个分区（块）
分析：因为有重复元素，可以考虑判断累加和的方式，排序后的数组前i个元素累加的和等于原数组前i个数累加的和时可以分为一个块～

Example 1:

Input: arr = [5,4,3,2,1]
Output: 1

Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
Example 2:

Input: arr = [2,1,3,4,4]
Output: 4

Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

一刷
题解：
如果把一个array的subarray视为一个整体(元素)，如果在array中的某个位置，所有左边的元素都小于右边的元素，那么可以形成新的chunk

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int[] maxOfLeft = new int[n];
        int[] minOfRight = new int[n];
        
        maxOfLeft[0] = arr[0];
        for(int i=1; i<n; i++){
            maxOfLeft[i] = Math.max(maxOfLeft[i-1], arr[i]);
        }
        
        minOfRight[n-1] = arr[n-1];
        for(int i=n-2; i>=0; i--){
            minOfRight[i] = Math.min(minOfRight[i+1], arr[i]);
        }
        
        int res = 0;
        for(int i=0; i<n-1; i++){
            if(maxOfLeft[i]<=minOfRight[i+1]) res++;
        }
        
        return res+1;
    }
}