题目名称

给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：

left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 的长度要尽可能小。
在完成这样的分组后返回 left 的 长度 。

用例可以保证存在这样的划分方法。

示例

输入：nums = [5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]

题解

先从左到右列出每位的最大值和从右到左每位的最小值，合成最大值数组和最小值数组
然后遍历数组，计算出第i为的最大值小于等于 i + 1 为的最小值
则left 的长度就是 i + 1

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {number}
 */
 var partitionDisjoint = function(nums) {
  let max = [nums[0]], min = [];
  min[nums.length-1] = nums[nums.length - 1]
  for(let i = 1; i < nums.length; i++) {
    if(max[i - 1] < nums[i]) {
      max[i] = nums[i] 
    } else {
      max[i] = max[i - 1]
    }
  }
  for(let i = nums.length - 2; i >= 0; i--) {
    if(min[i + 1] > nums[i]) {
      min[i] = nums[i] 
    } else {
      min[i] = min[i + 1]
    }
  }
  for(let i = 0; i < nums.length - 1; i++) {
    if(max[i] <= min[i + 1] ) {
      return i + 1
    }
  }
  return 1
};