Max Chunks To Make Sorted II

Max Chunks To Make Sorted II

问题

给定一个允许出现重复元素的数组，判断最多可以分成多少段，使得段与段之间都是有序的

解决方案

• 考虑到给出的数据的范围，这里时间复杂度应该控制在O(N)内，想到第二段（如果有的话），一定是在第一段的基础上进行判断的，这里可以构造一个排序数组
• 例如 [1,1,0,0,0,1]，我们可以构造为[2,3,0,1,4]，也就是用0 - length-1 的序号来表示这个数组，相同的元素按前后位置分配序号，这样问题就可以简化为一次遍历，对比下标
• 其实这里可以简化一点空间复杂度（也在O(N)范围内），我这里只是为了方便书写

class Solution {
    public int maxChunksToSorted(int[] arr) {
        if(arr.length<2)return arr.length;
        
        int max = Integer.MIN_VALUE,count = 0;
        
        //get index array like [1,2,3] or [5,2,2,3,1]
        int[] sorted = arr.clone();
        
        int[] newArr = new int[arr.length];
        
        Arrays.sort(sorted);
        
        int pre = -1;
        for(int i=0;i<sorted.length;i++){
            for(int j=0;j<arr.length;j++)
                if(arr[j]==sorted[i] && (i==0 || sorted[i]!=sorted[i-1] || pre<j)){
                    newArr[j] = i;
                    pre = j;
                    break;
                }
        }
        
        for(int i=0;i<arr.length;i++){
            max = Math.max(max,newArr[i]);
            if(max==i){
                count++;
            }
        }
        
        return count;
    }
}

• Sliding Window 这个方法我不大懂，希望看懂的人告诉我是怎么回事

• Sorted Count Pairs 其实类似我给出的方法，只不过使用Pair将相同的数字构造为一个对象，这样其实问题就简化成对一个没有连续相同元素的数组进行判断，对于这样的数组，直接对比相同位置上有序数组的元素和原数组当前位置之前（包括当前位置）的最大元素，就可以判断当前位置是否可以添加分段