leetcode - 分割数组的最大值

题目描述

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:数组长度 n 满足以下条件:

1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)

示例

输入:nums = [7,2,5,10,8]m = 2

输出:18

解释:一共有四种方法将nums分割为2个子数组。其中最好的方式是将其分为[7,2,5] 和 [10,8]，因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

题解

第一点，被分成的m个子数组的最大值必在nums的最大值和nums的元素之和之中。第二点，弱弱地猜猜看，拿所在区间范围的中间值去套，看看其能够得到多少个子区间数，如果说所得到的子区间数偏大于m，说明你划分的太小了，令左区间等于中间值加1，反之相反。

/**
* @param {number[]} nums
* @param {number} m
* @return {number}
*/
var splitArray = function(nums, m) {
var left = Math.max(...nums);
var right = nums.reduce((pre, cur) => pre + cur);
if (nums.length === m) {
  return left;
}
if (m === 1) {
  return right;
}

while(left < right) {
  var mid = (left + right) >> 1;
  var cnt = 1;
  var sum = 0;
  for (const val of nums) {
    if (sum + val > mid) {
      sum = 0;
      cnt++;
    }
    sum += val;
  }
  if (cnt > m) {
    left = mid + 1;
  } else {
    right = mid;
  }
} 
return left;
};

代码地址： https://zhengjiangtao.cn/coding/interview/split_array.js

项目地址： https://zhengjiangtao.cn/coding/interview/split_array.js

参考文献

410.分割数组的最大值(leetcode) ：https://leetcode-cn.com/problems/split-array-largest-sum