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