1011.在D天内送达包裹的能力

链接：1011.在D天内送达包裹的能力
难度：Medium
标签：数组、二分查找
简介：返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

题解 1 - typescript

• 编辑时间：2021-04-26
• 执行用时：1672ms
• 内存消耗：42.4MB
• 编程语言：typescript
• 解法介绍：二分查找，确定左右边界进行查找。

function shipWithinDays(weights: number[], D: number): number {
  let left = Math.max(...weights);
  let right = weights.reduce((total, cur) => total + cur, 0);
  while (left < right) {
    const mid = (left + right) >> 1;
    let curWeight = 0;
    let curDay = 1;
    for (const weight of weights) {
      if (curWeight + weight > mid) {
        curWeight = 0;
        curDay++;
      }
      curWeight += weight;
    }
    if (curDay > D) left++;
    else right = mid;
  }
  return left;
}