題目大意：給一個(gè)排列，可能有重復(fù)元素，我們將數(shù)組拆分成一些“塊”（分區(qū)），并對(duì)每個(gè)塊進(jìn)行單獨(dú)排序。連接它們之后，結(jié)果等于排序后的數(shù)組。問最多能夠分成多少個(gè)分區(qū)（塊）
分析：因?yàn)橛兄貜?fù)元素，可以考慮判斷累加和的方式，排序后的數(shù)組前i個(gè)元素累加的和等于原數(shù)組前i個(gè)數(shù)累加的和時(shí)可以分為一個(gè)塊～

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.

一刷
題解：
如果把一個(gè)array的subarray視為一個(gè)整體(元素)，如果在array中的某個(gè)位置，所有左邊的元素都小于右邊的元素，那么可以形成新的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;
    }
}