题目
给定一个数组 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 进行划分。
题解
拿到题首先想到是朴素的做法，就是每个点依次向左右扩展，如果发现左边的最大值一直小于右边的最小值，那么该点就是答案。但是该方法时间复杂度是O(n* n)，看一下数据量应该不能过。
那就想到通过离散化排序，我们把数组的下标保存，然后排序，从左往右再遍历下如果排序的最大值和下标相同，说明从左往右能组成连续的且排序小于右半部分的数组。该方法的时间复杂度是O(n*logn);
双指针的办法也是一开始就想到的，优先缩减右半部分，但是发现会缩过头。后来也是加上数组保存前缀最大值和后缀最小值，然后往后去修正。看了题解才感觉有点low,哈哈哈。
/**
* @param {number[]} nums
* @return {number}
*/
var partitionDisjoint = function(nums) {//离散化+排序
let arr = nums.map((val,index)=>({val,index}));
arr.sort((a,b)=>a.val-b.val);
let i = 0,max=-1;
for(;i<arr.length;i++){
max =Math.max(max,arr[i].index);
if(max === i) break;
}
return max+1;
}
var partitionDisjoint = function(nums) {//双指针
let left = 0,right = nums.length-1;
let leftMax = [nums[0]],rightMin = [];
rightMin[right] = nums[right];
while(left<right){
if(leftMax[left]<=rightMin[right]){
right--;
rightMin[right] = Math.min(rightMin[right+1],nums[right]);
}else{
left++;
leftMax[left] = Math.max(leftMax[left-1],nums[left]);
}
}
//console.log(left,right,leftMax,rightMin);
while(leftMax[left]>rightMin[++right]){
left++;
leftMax[left] = Math.max(leftMax[left-1],nums[left]);
}
return left+1;
};
