915. 分割数组（难度：中等）

题目链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals/

题目描述：

给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：

• left 中的每个元素都小于或等于 right 中的每个元素。
• left 和 right 都是非空的。
• left 的长度要尽可能小。

在完成这样的分组后返回 left 的 长度 。

用例可以保证存在这样的划分方法。

示例 1：

输入：nums = [5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]

示例 2：

输入：nums = [1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]

提示：

• 2 <= nums.length <= 105
• 0 <= nums[i] <= 106
• 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

解法一：小根堆（超时未通过）

使用小根堆来记录右边元素，目的是能快速得到最小值。依次取出一个元素放入左边，然后使用左边的最大值和右边小根堆堆顶元素（最小值）比较，判断是否满足条件。

但是，当数据量很大的时候，小跟堆的效率太低，超时了，仅供参考。

class Solution {
    public int partitionDisjoint(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 1; i < nums.length; i++) {
            queue.offer(nums[i]);
        }
        int result = 1;
        int max = nums[0];
        if (max <= queue.peek()) {
            return result;
        }
        for (int i = 1; i < nums.length; i++) {
            queue.remove(nums[i]);
            result++;
            max = Math.max(nums[i], max);
            if (max <= queue.peek()) {
                return result;
            }
        }
        return result;
    }
}

解法二：两次遍历

我们使用数组 temp 来记录右边元素的最小值，使用temp[i] 表示 nums[i] 到 nums[nums.length - 1] 的最小值。通过从右往左遍历一次，得到temp数组。再从左往右遍历一次，依次比较左边元素的最大值和右边元素的最小值temp[i + 1]。

代码：

class Solution {
    public int partitionDisjoint(int[] nums) {
        int[] temp = new int[nums.length];
        temp[nums.length - 1] = nums[nums.length - 1];
        for (int i = temp.length - 2; i >= 0; i--) {
            temp[i] = Math.min(nums[i], temp[i + 1]);
        }

        int leftMax = nums[0];

        for (int i = 0; i < nums.length; i++) {
            leftMax = Math.max(leftMax, nums[i]);
            if (leftMax <= temp[i + 1]) {
                return i + 1;
            }
        }
        return nums.length - 1;
    }
}