中等

问题描述

给定一个数组 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 进行划分。

一次遍历

使用 $leftMax$ 表示左子数组的最大值，$pos$ 表示左子数组的右边界，$currMax$ 为当前遍历过的元素的最大值。由于是从左到右遍历，当 $nums[i] < leftMax$ 时，说明当前边界 $pos$ 不能保证右侧元素皆小于左侧元素，此时更新 $leftMax$ 和 $pos$ 的值，由于一直记录这当前遍历过的元素最大值，因此 $leftMax$ 更新为 $currMax$，$pos$ 更新为 $i$。最终遍历完后，左侧子数组的长度即为 $pos + 1$。

/**
 * @param {number[]} nums
 * @return {number}
 */
var partitionDisjoint = function (nums) {
  const n = nums.length
  let leftMax = nums[0]
  let currMax = nums[0]
  let pos = 0
  for (let i = 0; i < n; i++) {
    currMax = Math.max(currMax, nums[i])
    if (nums[i] < leftMax) {
      leftMax = currMax
      pos = i
    }
  }
  return pos + 1
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$