题目大意:给一个排列,可能有重复元素,我们将数组拆分成一些“块”(分区),并对每个块进行单独排序。连接它们之后,结果等于排序后的数组。问最多能够分成多少个分区(块)
分析:因为有重复元素,可以考虑判断累加和的方式,排序后的数组前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;
}
}