【数组】最多能完成排序的块数学

题目描述

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1:

输入: arr = [1, 4, 0, 2, 3, 5]
输出: 2
解释:
我们可以把它分成两块，例如 [1, 4, 0, 2, 3], [5]。

解题思路

这道题给定的数组里面的数字是唯一的，范围: [0, N-1]。

参考其他人的解决思路如下，这里使用 [1, 4, 0, 2, 3, 5] 举例：

找出指定范围内的最小值，从0开始查找；
找到最小值的下标：i，以及最大值：max；
从 i 到 max 继续遍历，找到里面的最大值；
使用max+1作为最小值，重复第1、2、3、4步骤，直到所有数字均遍历完成。

按照上述思路代码实现如下：


 
class Solution {
 
    public int maxChunksToSorted(int[] arr) {
 
        int count = 0;
        int targetValue = 0;
        int i = 0;
        while (i < arr.length) {
            int max = arr[i];
            int index = findNextIndex(i, targetValue, arr, max);
 
            if (index > arr.length - 1) {
                break;
            }
            targetValue = index + 1;
            i = index + 1;
            count++;
        }
        return count;
    }
 
    private int findNextIndex(int i, int targetValue, int[] arr, int max) {
        for (; i < arr.length; i++) {
            max = Math.max(arr[i], max);
            if (targetValue == arr[i]) {
                return i > max ? i : queryMax(i, arr, max);
            }
        }
        return arr.length;
    }
 
    private int queryMax(int i, int[] arr, int max) {
        while (i <= max) {
            max = Math.max(arr[i], max);
            i++;
        }
        return i - 1;
    }
 
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxChunksToSorted(new int[]{4, 3, 2, 1, 0}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 0, 2, 3, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 0, 3, 2, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 3}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 3, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 4, 3}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 4, 3, 5}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 5, 3, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 2, 0, 3}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 4, 0, 2, 3, 5}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 5, 3, 0, 2, 8, 7, 6, 4}));
    }
}

上述代码复杂度比较高，理解成本很高，于是考虑使用其他的方案：

从下标0开始，找这个下标对应value的最大值；
完成上述操作后，重复执行，直到遍历完成。

代码实现如下：


 
class Solution {
 
    public int maxChunksToSorted(int[] arr) {
 
        int max = arr[0];
        int count = 0;
 
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, i);
            if (max == arr[i]) {
                count++;
            }
        }
 
        return count;
    }
 
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxChunksToSorted(new int[]{4, 3, 2, 1, 0}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 0, 2, 3, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 0, 3, 2, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 3}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 3, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 4, 3}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 4, 3, 5}));
        System.out.println(solution.maxChunksToSorted(new int[]{2, 0, 1, 5, 3, 4}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 2, 0, 3}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 4, 0, 2, 3, 5}));
        System.out.println(solution.maxChunksToSorted(new int[]{1, 5, 3, 0, 2, 8, 7, 6, 4}));
    }
}

总结

这道题是一个中等难度题目，第一种方案自己想到了，最终完成了代码。第二种方案，代码非常简单，但最终还是看其他人的代码实现才解决了。这道题的解决方案欢迎大家回复，给出更加优秀和简单的解法。

新版题目描述

下面加大这道题的难度，下面是题目描述：

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

示例1:

输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

新版题目解题思路

由于这道题是之前题目的增强版本，我这边思路是复用上面的解题思路：

将arr拷贝到copy中；
对copy进行排序；
记录排序后copy的位置；
按照arr的顺序对arr的位置进行还原；
按照非重复的数组，获得数组能分成的最多块数量。

按照上述思路代码实现如下：


 
import java.util.*;
 
class Solution {
    public int maxChunksToSorted(int[] arr) {
 
 
        // 拷贝数组
        int[] copy = Arrays.copyOf(arr, arr.length);
 
        // 对数组排序
        Arrays.sort(copy);
 
        // 记录数组位置
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < copy.length; i++) {
            List<Integer> list = map.get(copy[i]);
            if (list == null) {
                list = new LinkedList<>();
                map.put(copy[i], list);
            }
            list.add(i);
        }
 
 
        // 还原数组index
        int[] array = new int[arr.length];
        for (int i = 0; i < arr.length; ) {
            List<Integer> list = map.get(arr[i]);
            array[i] = list.remove(0);
            i++;
        }
 
        // array就是从[0,N-1]的数组
        int count = 0;
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            max = Math.max(array[i], max);
            if (max == i) {
                count++;
            }
        }
        return count;
    }
 
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxChunksToSorted(new int[]{2, 1, 3, 4, 4}));
    }
}

使用单调栈解决

case1:

case2: 将这个位置的2替换成0，如下图：

思路如下：

确保每一组数中，第一个数都是最大的；
利用单调栈来处理，如果value比栈顶数据大则入栈，否则记录出栈记录该值为current，用value和剩余栈中元素比较，如果. value<剩余栈中元素那么元素出栈；