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 <= 10^5
• 0 <= nums[i] <= 10^6

解析

遍历数组，维护当前最大值和分割点最大值。当当前元素小于分割点最大值时，需要更新分割点。

var partitionDisjoint = function (nums) {
  let leftMax = nums[0];
  let max = nums[0];
  let partition = 0;

  for (let i = 1; i < nums.length; i++) {
    max = Math.max(max, nums[i]);
    if (nums[i] < leftMax) {
      partition = i;
      leftMax = max;
    }
  }

  return partition + 1;
};

时间复杂度 O(n)，空间复杂度 O(1)。