915.分割数组

915.分割数组

Category	Difficulty	Likes	Dislikes
algorithms	Medium (47.27%)	187	-

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

---

Discussion | Solution

思路

遍历两次：第一次从头拿到左边数组最大值，从尾巴开始拿到右边数组最小的值。第二次，从头开始找，找到第一个左边数组最大值大于下一个元素右边数组最小值的下标返回即可。

解答

/*
 * @lc app=leetcode.cn id=915 lang=javascript
 *
 * [915] 分割数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var partitionDisjoint = function (nums) {
  const arr = new Array(nums.length).fill().map(() => ({}));
  let max = -Infinity,
    min = Infinity;
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i],
      num2 = nums[nums.length - 1 - i];
    max = Math.max(num, max);
    arr[i].left = max;
    min = Math.min(num2, min);
    arr[nums.length - 1 - i].right = min;
  }
  for (let i = 0; i < arr.length - 1; i++) {
    const { left } = arr[i];
    const { right } = arr[i + 1];
    if (right >= left) {
      return i + 1;
    }
  }
};
// @lc code=end