1. 题面

给定一个数组 nums ，将其划分为两个连续子数组left和right，使得：

left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 的长度要尽可能小。
在完成这样的分组后返回left的长度。

用例可以保证存在这样的划分方法。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 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 进行划分。

2. 题目分析

题目的要求是从nums中找到一个i，使得nums[i]左边的元素全部要小于等于右边的元素。

那么从可能性上来讲从0~n-1中的每个元素都有可能是这个分割点，所以我们只需要枚举这个分割点即可。

由于题目说了肯定能够找到一种划分方法，使得left和right数组不为null

这就是基本思路，我们只需要枚举每个分割点的位置，然后进行验证即可。

现在的问题是如何验证得高效?目前已经知道题目的length是10的5次方,如果按照常规思路去验证的话(从分割点从左出发,向右出发,肯定是n次的访问),最终就是n方的复杂度,肯定是通过不了这个题目的。

但是如果我们能够通过提前知道[0,i]的最大值，(i,n-1]的最小值，然后判断是从最大值是小于最小值的，这样的话就能够快速判断了。

那么如何来实现这个事情呢?

[0,i]区间内的最大值如何求解?

很简单,一次遍历即可,从0开始遍历,我们定义一个preMax[]，用来记录每一个i的位置下的最大值。

preMax[0] = nums[0];//base-case
for(int i = 1;i<n;i++){
    preMax[i] = Math.max(preMax[i-1],nums[i]);
}

[i,n-1]区间内的最小值如何求解?

与求最大值类似,只不过遍历方向变了而已，看代码

suffixMin[n-1] = nums[n-1];
for(int i = n-2;i>=0;i--){
    suffixMin[i] = Math.min(suffixMin[i+1],nums[i]); 
}

以上的代码可以合并为一段

int n = nums.length;
int[][] pre = new int[n+1][2];
//pre[i][0]:是[0,i]的最大值
//pre[i][1]:是[i,n-1]的最小值
pre[0][0] = nums[0];
pre[n-1][1] = nums[n-1];
//枚举left数组
for(int i = 1;i<=n-1;i++){
    pre[i][0] = Math.max(pre[i-1][0],nums[i]);
    if(i>=2){
        //就执行这个
        System.out.println(pre[n-i+1][1]+":"+nums[n-i]);
        pre[n-i][1] = Math.min(pre[n-i+1][1],nums[n-i]);
    }
}
//边界:n-i
//i==n-1,此时j=n-(n-1)=n-n+1=1
//还差个0
pre[0][1] =Math.min(pre[1][1],nums[0]);

3. 题解代码

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[][] pre = new int[n+1][2];
        //pre[i][0]:是[0,i]的最大值
        //pre[i][1]:是[i,n-1]的最小值
        pre[0][0] = nums[0];
        pre[n-1][1] = nums[n-1];
        //枚举left数组
        for(int i = 1;i<=n-1;i++){
            pre[i][0] = Math.max(pre[i-1][0],nums[i]);
            if(i>=2){
                //System.out.println(pre[n-i+1][1]+":"+nums[n-i]);
                pre[n-i][1] = Math.min(pre[n-i+1][1],nums[n-i]);
            }
        }
        //边界:n-i
        //i==n-1,此时j=n-(n-1)=n-n+1=1
        //还差个0
        pre[0][1] =Math.min(pre[1][1],nums[0]);
        //然后开始枚举分界点
        int left = Integer.MIN_VALUE;
        for(int i = 0;i<n-1;i++){
            //左边数组的最大值要小于等于右边数组的最小值
            //System.out.println(pre[i][0]+" "+pre[i+1][1]);
            if(pre[i][0] <= pre[i+1][1]){
                //结算此时的i
                left = i+1;
                break;
            }
        }
        return left;
    }
}