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

分割数组的最大值

题目

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

思路（答案二分）

要把数组分成 m 段，使得“每段和的最大值”最小。

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

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

check(x) 用贪心：从左到右累加，超过 x 就切一段。

边界：

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

代码（JavaScript）

function canSplit(nums, m, limit) {
  let parts = 1;
  let cur = 0;
  for (const x of nums) {
    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;
};