Given an array arr that is a permutation of [0, 1, ..., arr.length - 1] , we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.
What is the most number of chunks we could have made?
Example 1:
Input: arr = [4,3,2,1,0] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn’t sorted.
Example 2:
Input: arr = [1,0,2,3,4] Output: 4 Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
Note:
-
arrwill have length in range[1, 10]. -
arr[i]will be a permutation of[0, 1, ..., arr.length - 1].
思路
假设有数组arr[]，用i索引遍历数组，0~arr.length，res代表计数器
维护一个最大值max，这个最大值就是分组结界的判断依据：
比如1 4 2 3
- 当i == 0时，max = 0，此时 i == max，说明 i 之前的元素都小于 max，i 就是第二个分组，当i >= 1时，max是4，4就是第二个分组结界的判断依据，当 i == max时，说明 i 之前的元素都小于 max，i 就是第二个分组。
遍历数组并进行判断：
- 如果max == i，说明 i 之前的元素的值都小于等于 i（或者max）：arr[0], arr[1],…,arr[i-1]都小于等于max，i是分组的结界，于是res+=1
- 如果max != i，说明arr[i]要小于max，i不是分组的结界，res不变
i = 0, max = 3, res = 0
| 3 | 4 | 0 | 1 | 2 |
|---|---|---|---|---|
| i |
i = 1, max = 4, res = 0
| 3 | 4 | 0 | 1 | 2 |
|---|---|---|---|---|
| - | i |
i = 2, max = 4, res = 0
| 3 | 4 | 0 | 1 | 2 |
|---|---|---|---|---|
| - | - | i |
i = 3, max = 4, res = 0
| 3 | 4 | 0 | 1 | 2 |
|---|---|---|---|---|
| - | - | - | i |
i = 4, max = 4, res = 1
| 3 | 4 | 0 | 1 | 2 |
|---|---|---|---|---|
| - | - | - | - | i |
java
class Solution {
public int maxChunksToSorted(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int count = 0, max = 0;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
if (max == i) {
count++;
}
}
return count;
}
}
python
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
return sum(max(arr[:i+1]) == i for i in range(len(arr)))