如何解析力扣算法题中的数组分割策略？

本文共计322个文字，预计阅读时间需要2分钟。

给定一个数组nums，将其划分为两个连续的子数组left和right，使得left中每个元素都小于或等于right中的每个元素。

给定一个数组​​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]

代码：

class Solution {
public int partitionDisjoint(int[] nums) {
int len = nums.length;

int rec=0;
int max1=nums[0];
int max2=max1;
for(int i=0;i<len;i++){
if(max1>nums[i]){
max1 = max2;
rec=i;
}else max2 = Math.max(max2,nums[i]);
}
return rec+1;
}
}

思路：

用rec记录边界，当遍历的i小于max1的时候更新边界，大于的时候更新max2，当后边的遍历过程中再有小于max1的时候更新max1为max2，因为max2记录的前边的最大值。