0915. 分割数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 一次遍历

1. 📝 题目描述

• leetcode

给定一个数组 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
• 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

2. 🎯 s.1 - 一次遍历

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} nums
 * @return {number}
 */
var partitionDisjoint = function (nums) {
  let leftMax = nums[0]
  let curMax = nums[0]
  let partitionIdx = 0

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

  return partitionIdx + 1
}

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 维护 leftMax（左部分最大值）、curMax（当前全局最大值）以及分割点索引 partitionIdx
• 遍历数组，如果当前元素小于 leftMax，说明当前元素必须属于左部分，更新分割点并将 leftMax 更新为 curMax
• 否则更新 curMax
• 返回 partitionIdx + 1