友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
915. 分割数组
给定一个数组 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进行划分。
思路分析
两次遍历，先从右向左查找最小值，然后从左向右查找最大值，当最大值小于下一个的最小值，则就到了分界线。
下面这个题解更简单，只需要遍历不到一遍：
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-26 11:39:29
*/
public int partitionDisjoint(int[] nums) {
int length = nums.length;
int[] ext = new int[length];
ext[length - 1] = nums[length - 1];
int min = nums[length - 1];
for (int i = length - 2; i >= 0; i--) {
min = Math.min(min, nums[i]);
ext[i] = min;
}
int max = nums[0];
for (int i = 0; i < length - 1; i++) {
max = Math.max(max, nums[i]);
if (max <= ext[i + 1]) {
return i + 1;
}
}
return length - 1;
}
参考资料
-
915. 分割数组 - 【爪哇缪斯】图解LeetCode — 不到一遍的遍历，牛逼！