- 题目描述：
- 数组arr是[0, 1, …, arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
- 问；我们最多能将数组分成多少块？
- class Solution {
- public int maxChunksToSorted(int[] arr) {
- int ans=0;//用来统计块的个数
- int max=arr[0];
- for(int i=0;i<arr.length;i++){
- max=Math.max(max,arr[i]);//统计前i+1个元素中的最大值
- if(max==i){//当遍历到第i个位置时，如果当前下标值为目前数组中的最大值，则说明可以分成一块
- ans++;
- }
- }
- return ans;
- }
- }
题目描述：
数组arr是[0, 1, …, arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
问；我们最多能将数组分成多少块？
解题思路：
当遍历到第i个位置时，如果可以切成快，那满足前i+1个元素的最大值一定等于i。否则一定有比i还要小的数组值被强制划分到后面的块去了，这样排序出来的各个块连起来 不满足全局升序。
class Solution {
public int maxChunksToSorted(int[] arr) {
int ans=0;//用来统计块的个数
int max=arr[0];
for(int i=0;i<arr.length;i++){
max=Math.max(max,arr[i]);//统计前i+1个元素中的最大值
if(max==i){//当遍历到第i个位置时，如果当前下标值为目前数组中的最大值，则说明可以分成一块
ans++;
}
}
return ans;
}
}
若有收获，就点个赞吧
0 人点赞
