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

约 7 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 阿里巴巴 快手 亚马逊
标签
数组 二分查找
目录

题目描述

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

题意分析

传送带上按顺序排着一批包裹，船每天从传送带上依次取货装船，装到当天运力上限就发船，第二天接着从断点继续。要求在不超过 days 天内把所有包裹运完，问船的运载能力最小是多少。

「按顺序」这三个字是硬约束：不能挑轻的先运，也不能重排包裹，所以每一天装的必然是原数组里的一段连续区间。这把问题变成了「把数组切成至多 days 段，使各段和的最大值最小」。

约束信号：包裹数量最多 $5 \times 10^4$，单个重量最多 500，天数不超过包裹数量。运力的取值范围是一个连续整数区间，最大不过 $2.5 \times 10^7$，直接从小到大逐个试要试上千万次、每次还要 $O(n)$ 模拟，必然超时——但这个「逐个试」的框架本身是对的，只是需要换成对数级的搜索方式。

边界情况：运力必须至少等于最重的那个包裹，否则它永远装不上船；运力达到全部包裹总重时一天就能运完；days 等于包裹数时，每天运一个，答案就是最重的包裹。

解法：二分答案运载能力

核心思路

问题关键：包裹不能重排，每天只能装载尚未运输序列的一段前缀。题目等价于把数组按顺序切成不超过 days 段，使「最大段和」尽可能小。

选法依据：给定运力 capacity 后，可以线性判断需要多少天。运力越大，所需天数只会减少，不会增加，因此可行性随运力呈「不可行……可行」的单调序列，适合二分第一个可行值。

判定与证明：固定运力后，每天尽量装入最长前缀，下一件放不下才开新的一天。设贪心与任意合法方案都完成了前 $k$ 天，贪心运走的包裹数不会更少：第 $k+1$ 天继续装最长可装前缀，优势仍然保持。由归纳可知，贪心使用的天数最少；因此它需要的天数不超过 days，当且仅当该运力可行。

二分不变量：闭区间 [left, right] 始终包含最小可行运力。left 初始为最重包裹，低于它必然装不下；right 初始为总重量，一天即可运完。若 mid 可行，答案仍可能是 mid，令 right = mid；否则 mid 及其左侧都被排除，令 left = mid + 1。

当 left == right 时，区间只剩一个候选。根据不变量，它就是最小可行运力。

解题步骤

  • 扫描 weights，令 left 为最大重量、right 为总重量，得到一不可再小的下界和一个必然可行的上界。
  • 当 left < right 时，计算 mid = left + (right - left) / 2，避免左右边界直接相加。
  • 用 canShip 模拟运力 mid：当天还能装就继续装，超出运力就开启新的一天；若所需天数超过 days，可提前返回 false。
  • mid 可行时令 right = mid，保留它并继续寻找更小值；不可行时令 left = mid + 1。
  • 区间每轮至少缩小一个整数，最终 left == right，返回该值。

例子：weights = [1,2,3,4,5,6,7,8,9,10]、days = 5 时，初始区间为 [10,55]。二分依次判定 32（可行）、21（可行）、15（可行）、12（不可行）、14（不可行），最终收敛到 15。运力 15 可分为 [1,2,3,4,5]、[6,7]、[8]、[9]、[10]；而 14 至少需要 6 天，所以 15 恰为最小值。

代码实现

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 0;
        for (int weight : weights) {
            left = Math.max(left, weight);
            right += weight;
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canShip(int[] weights, int days, int capacity) {
        int usedDays = 1;
        int load = 0;
        for (int weight : weights) {
            // 当前天放不下时，必须开启新的一天。
            if (load + weight > capacity) {
                usedDays++;
                load = 0;
                if (usedDays > days) {
                    return false;
                }
            }
            load += weight;
        }
        return true;
    }
}

func shipWithinDays(weights []int, days int) int {
    left := 0
    right := 0
    for _, weight := range weights {
        if weight > left {
            left = weight
        }
        right += weight
    }

    for left < right {
        mid := left + (right-left)/2
        if canShip(weights, days, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canShip(weights []int, days int, capacity int) bool {
    usedDays := 1
    load := 0
    for _, weight := range weights {
        // 当前天放不下时，必须开启新的一天。
        if load+weight > capacity {
            usedDays++
            load = 0
            if usedDays > days {
                return false
            }
        }
        load += weight
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n \log R)$，其中 $n$ 是包裹数量，$R = \sum weights - \max(weights) + 1$ 是候选运力个数。二分进行 $O(\log R)$ 轮，每轮最多扫描全部包裹。
  • 空间复杂度：$O(1)$，只维护二分边界、当天载重和已用天数。

关键点总结

  • 看到「最小化最大段和」，先检查能否把答案当作阈值，并构造单调的可行性判定。
  • 判定函数不是随意模拟：固定运力时，每天装最长前缀能让已运走的包裹数始终不少于其他方案，因此使用天数最少。
  • 二分边界应同时满足业务含义：最大单件重量是最低可能值，总重量是必然可行值。
  • while (left < right)、right = mid、left = mid + 1 是一套完整的「寻找第一个可行值」模板，不要混用其他边界写法。
  • 面试中要明确「至多 days 天」：提前运完当然可行，不需要恰好用满天数。

易错点总结

  • 下界过小：left 若小于最大单件重量，判定函数可能把装不下的包裹也放入新一天。直接取最大重量可从定义上排除无效容量。
  • 天数从 0 开始：只要数组非空就至少使用一天，usedDays 应初始化为 1。
  • 边界条件写成大于等于：load + weight == capacity 时仍能装下，不应开启新一天。[5,5] 在运力 10、一天限制下应当可行。
  • 二分更新不前进：不可行时写 left = mid，在 left + 1 == right 时会死循环，必须排除 mid，写成 mid + 1。
  • 要求恰好用满天数：可行条件是 usedDays <= days。更早运完仍满足「在 days 天内送达」。
  • 改变包裹顺序：排序会改变每天对应的连续段，已经不再是原题，判定必须按输入顺序扫描。

相似题目

题目 难度 考察点
69. x 的平方根 简单 在整数上二分平方值，判定条件是一次乘法
LCR 072. x 的平方根 简单 69 的同题改编，注意溢出与向下取整
875. 爱吃香蕉的珂珂 中等 判定函数是各堆向上取整之和，与顺序无关
LCR 073. 爱吃香蕉的狒狒 中等 875 的同题改编，重点在上界取最大堆而非总和
1482. 制作 m 束花所需的最少天数 中等 二分天数，判定要数连续可用花的段长
1552. 两球之间的磁力 中等 最大化最小间距，判定改为贪心放球计数
1201. 丑数 III 中等 判定用容斥计数，涉及最小公倍数与溢出
LCP 12. 小张刷题计划 中等 每段可免去一题耗时，判定需在段内记录最大值
410. 分割数组的最大值 困难 与本题完全同模型，另有区间 DP 解法可对照
644. 子数组最大平均数 II 困难 在实数域二分，判定靠减去均值后的前缀和
668. 乘法表中第k小的数 困难 二分数值，判定统计不超过它的元素个数
719. 找出第 K 小的数对距离 困难 二分距离，判定用双指针统计数对数量
774. 最小化去加油站的最大距离 困难 在实数域二分间距，判定累加所需新增站数
878. 第 N 个神奇数字 困难 判定用容斥求倍数个数，答案还需取模
1231. 分享巧克力 困难 最大化最小段和，判定贪心切分并计段数