題目大意：給一個排列，可能有重復元素旨涝，我們將數(shù)組拆分成一些“塊”（分區(qū)），并對每個塊進行單獨排序侣背。連接它們之后白华，結果等于排序后的數(shù)組。問最多能夠分成多少個分區(qū)（塊）
分析：因為有重復元素贩耐，可以考慮判斷累加和的方式弧腥，排序后的數(shù)組前i個元素累加的和等于原數(shù)組前i個數(shù)累加的和時可以分為一個塊～
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;
}
}
