915.分割数组.md

915.分割数组

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

// @lc code=start
function partitionDisjoint(nums: number[]): number {}
// @lc code=end

解法 1: 预处理后缀最小值

function partitionDisjoint(nums: number[]): number {
  const r: number[] = [],
    n = nums.length
  let min = Infinity
  for (let i = n - 1; i >= 0; i--) {
    r[i] = min
    min = Math.min(min, nums[i])
  }
  let max = 0
  for (let i = 0; i < n; i++) {
    max = Math.max(max, nums[i])
    if (max <= r[i]) return i + 1
  }
  return -1
}

Case

test.each([
  { input: { nums: [5, 0, 3, 8, 6] }, output: 3 },
  { input: { nums: [1, 1, 1, 0, 6, 12] }, output: 4 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(partitionDisjoint(nums)).toEqual(output)
})