LeetCode 768. 最多能完成排序的块 II（java）

本文主要是介绍LeetCode 768. 最多能完成排序的块 II（java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.问题

给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。

arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

原题链接；

2.解法

class Solution {public int maxChunksToSorted(int[] arr) {// abnormalif(arr.length < 1) return 0;// find the first satisfy the resultint index = 0;int count = 0;while(index < arr.length){//递归寻找切割点，index为当前切割点index = indexToCut(arr, index);count++;}return count;}public int indexToCut(int[] arr, int index){int maxNum = arr[index];int markIndex = index;int beforeIndex = index;//如果当前切割点前的最大值均比后面的值小或等于，则满足for(int i = index + 1; i< arr.length; i++){if(arr[i] >= maxNum){continue;}//后面有更小的值，则更新切割点和遍历新旧切割点的值，更新新切割点之前的最大值。else{beforeIndex = markIndex;markIndex = i;for(int j = beforeIndex; j<markIndex; j++){if(arr[j] > maxNum){maxNum = arr[j];}}}}return markIndex + 1;}
}

时间复杂度 O(n^2); 空间复杂度 O(n)(递归复制数组）;

解法2：

import java.util.Arrays;
class Solution {public static int maxChunksToSorted(int[] arr) {int len=arr.length;//存从左往右最大值,每个位置都存int[] leftmax=new int[len];//存从右往左最小值int[] rightmin=new int[len];int  count=1;leftmax[0]=arr[0];rightmin[len-1]=Integer.MAX_VALUE;for(int i=1;i<len;++i){leftmax[i]=Math.max(leftmax[i-1],arr[i]);}//每个i位置存的是i+1以后的最大值for(int j=len-2;j>=0;--j){rightmin[j]=Math.min(rightmin[j+1], arr[j+1]);}for(int index=0;index<len-1;++index){if(leftmax[index]<=rightmin[index]){count++;}}return count;}}