Skip to content

768. Max Chunks To Make Sorted II

768. Max Chunks To Make Sorted II

题目: https://leetcode.com/problems/max-chunks-to-make-sorted-ii/

难度: Hard

题意：

  1. 给定一个数组，求最多能够将数组分成多少段，使得每段排序之后连接起来，是一个有序数组

思路：

  • 显而易见，数据能否分的条件是，分出来的左边数组的最大值不大于比右边数组的最小值
  • 只需要扫描一下，先把最大值和最小值数组预处理出来，然后遍历就可以得出结果

解法：

class Solution {
     public int maxChunksToSorted(int[] arr) {
        int[] min = new int[arr.length];
        int[] max = new int[arr.length];
        max[0] = arr[0];
        for (int i = 1;i < arr.length;i++) {
            max[i] = Math.max(arr[i], max[i - 1]);
        }
        min[arr.length - 1] = arr[arr.length - 1];
        for (int i = arr.length - 2;i >= 0;i--) {
            min[i] = Math.min(arr[i], min[i + 1]);
        }
        int ret = 1;
        for (int i = 0;i + 1 < arr.length;i++) {
            if (max[i] <= min[i + 1]) {
                ret++;
            }
        }
        return ret;
    }
}
回到顶部