LeetCode_数组_中等_915.分割数组

1.题目

给定一个数组 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 <= 10⁵
0 <= nums[i] <= 10⁶
可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals

2.思路

（1）辅助数组
要想满足题目中的三个条件，比较容易想到的方法是：
① 设 left 和 right 中的最大值和最小值分别为 leftMax、rightMin，left 的长度为 res；
② 从 left = [nums[0]]，right = [nums[1]…nums[length - 1]] 开始划分，如果 leftMax ≤ rightMin，那么直接返回 res 即可；否则就扩大 left，缩小 right，同时更新 leftMax、rightMin 和 res；
③ 由于题目保证至少有一种方法能够按题目所描述的那样对 nums 进行划分，所以在划分的过程中一定可以返回 res；

现在的关键是在划分的过程中如何确定 leftMax、rightMin 和 res 这三者的值。
① 对于 res 来说，其初始值肯定为 1，并且 left 每扩大一次（指多加入一个元素），res 就加一；
② 对于 leftMax 来说，其初始值为 nums[0]，当 left 每加入一个元素 nums[i] 时，leftMax 更新为 leftMax 和 nums[i] 之间的最大值即可；
③ 对于 rightMin 来说，可以通过辅助数组来保存 right（即 nums[i…length - 1]，1 ≤ i ≤ length）中的最小值，辅助数组定义如下：

int[] rightMin = new int[length];
1

在划分之前，我们需要初始化该辅助数组：

Arrays.fill(rightMin, Integer.MAX_VALUE);
rightMin[length - 1] = nums[length - 1];
for (int i = length - 2; i >= 1; i--) {
    rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
}
1
2
3
4
5

（2）无需辅助数组，一次遍历
思路参考该 LeetCode 用户题解。

① 设 max 表示 nums[0…i] 中的最大值，leftMax 表示子数组 left 中的最大值，初始值为 nums[0]；
② 开始遍历 nums，在遍历的过程中先更新 max，然后再判断当前数 nums[i] 与 leftMax 的大小：
1）如果 nums[i] < leftMax，那么则需要将 nums[i] 划分到 left 中，同时更新 leftMax 和 res；
2）如果 nums[i] ≥ leftMax，那么 nums[i] 可以暂时存放到 right 中（该部分无需在代码中体现）；
③ 遍历结束后，返回 res + 1 即可，需要注意的是这里的 res 保存的是下标而并非长度，所以在返回长度时需要加一。

3.代码实现（Java）

//思路1————辅助数组
class Solution {
    public int partitionDisjoint(int[] nums) {
        int length = nums.length;
        // res 记录 left 的长度，初始值为 1
        int res = 1;
        // leftMax 表示子数组 left 中的最大值
        int leftMax = nums[0];
        // rightMin[i] 表示子数组 right (即 nums[i...length - 1])中的最小值
        int[] rightMin = new int[length];
        //初始化 rightMin
        Arrays.fill(rightMin, Integer.MAX_VALUE);
        rightMin[length - 1] = nums[length - 1];
        for (int i = length - 2; i >= 1; i--) {
            rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
        }
        //开始划分
        for (int i = 1; i < length; i++) {
            if (leftMax <= rightMin[i]) {
                // left 中的最大值小于等于 right 中的最小值，那么直接返回 res
                return res;
            } else {
                // 扩大 left，缩小 right，同时更新 leftMax 和 res
                leftMax = Math.max(leftMax, nums[i]);
                res++;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//思路2————无需辅助数组，一次遍历
class Solution {
    public int partitionDisjoint(int[] nums) {
        int length = nums.length;
        int res = 0;
        // max 表示 nums[0...i] 中的最大值
        int max = Math.max(nums[0], nums[1]);
        // leftMax 表示子数组 left 中的最大值
        int leftMax = nums[0];
        for (int i = 0; i < length; i++) {
            max = Math.max(max, nums[i]);
            if (nums[i] < leftMax) {
                //如果当前数 nums[i] 小于 leftMax，则需要将其划分到 left 中
                leftMax = max;
                //同时更新 res
                res = i;
            }
        }
        return res + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21