[!info] related notes 算法面试题型 MOC 二分查找 贪心算法

分割数组的最大值

题目

410. 分割数组的最大值 - 力扣（LeetCode）

思路（答案二分）

把非空非负整数数组分成恰好 m 个非空连续子数组，1 ≤ m ≤ nums.length，使最大段和最小。不是任意重排分组。

二分答案 x = 最大段和上限：

• check(x)：能否在“每段和 <= x”的约束下，把数组分成不超过 m 段
• 单调性：x 越大越容易满足

check(x) 从左到右尽量延长当前段，超过 x 才切段；在非负前提下得到所需的最少段数。若少于 m 段，可继续拆分而不增大最大段和，所以“至多 m 段可行”足以判断“恰好 m 段可行”。负数输入不能沿用这个贪心证明与边界。

边界：

• lo = max(nums)（每段至少包含一个元素）
• hi = sum(nums)（不切分就是一段）

代码（JavaScript）

function canSplit(nums, m, limit) {
  let parts = 1;
  let cur = 0;
  for (const x of nums) {
    if (x > limit) return false;
    if (cur + x <= limit) {
      cur += x;
    } else {
      parts++;
      cur = x;
      if (parts > m) return false;
    }
  }
  return true;
}

var splitArray = function(nums, m) {
  let lo = 0;
  let hi = 0;
  for (const x of nums) {
    lo = Math.max(lo, x);
    hi += x;
  }

  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (canSplit(nums, m, mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
};