LeetCode_数组_中等_915.分割数组
目录
- 1.题目
- 2.思路
- 3.代码实现(Java)
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 <= 105
0 <= nums[i] <= 106
可以保证至少有一种方法能够按题目所描述的那样对 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];
在划分之前,我们需要初始化该辅助数组:
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]);
}
(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;
}
}
//思路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;
}
}