给定一个数组 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 进行划分。
- 利用minv来记录后缀最小值，当某个位置前面所有数的最大值<=后面所有数的最小值时该位置便是答案。
- 时间复杂度O(n)
- 空间复杂度O(n)
class Solution {
public int partitionDisjoint(int[] nums) {
int n = nums.length, maxv = nums[0];
int[] minv = new int[n];
minv[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) minv[i] = Math.min(nums[i], minv[i + 1]);
for (int i = 0; i < n; i++) {
if (maxv <= minv[i + 1]) return i + 1;
maxv = Math.max(nums[i], maxv);
}
return n;
}
}- 优化：我们通过maxv来保存左边数组的最大值，pos代表最后一个元素位置，若当前元素nums[i]比maxv小，那么代表已经构建的数组不满足要求，更新位置为当前的数，并更新左边数组最大值
- 时间复杂度O(n)
- 空间复杂度O(1)
class Solution {
public int partitionDisjoint(int[] nums) {
int n = nums.length, maxv = nums[0], cur_maxv = nums[0], pos = 0;
for (int i = 0; i < n; i++) {
cur_maxv = Math.max(nums[i], cur_maxv);
if (nums[i] < maxv) { //代表和已经划分数组的位置冲突, 更新位置
maxv = cur_maxv;
pos = i;
}
}
return pos + 1;
}
}