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

约 6 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 阿里 亚马逊 百度 快手
标签
数组 二分查找

题目描述

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

image-20260929000459300

image-20260929000459301

题意分析

包裹必须保持原顺序，不能拆分；每天运走其中连续的一段，重量之和不能超过船的运力。要求在至多 days 天内全部运完，求满足条件的最小运力。

直接寻找最优分组不容易，但给定一种运力，可以顺序模拟它至少需要多少天，再判断这个运力是否足够。

解法：二分答案运载能力

核心思路

[!blue]

先解决“运力为 capacity 时能否按时运完”。从第一天开始，按顺序尽量装包裹；只有下一件会使当天超重，才开启新一天，并把这一件装入新的一天。

这个贪心会得到最少天数：第一天取的是容量内最长前缀，其他安排不可能运得更多。若前几天贪心已经运得不少于另一种安排，那么下一天从更靠后的包裹开始，至少也能运到另一种安排当天的末尾，因为跳过的包裹重量都是正数。因此贪心每天的进度都不会落后，所用天数也不会更多。

运力越大，所需天数不会增加：较小运力下的装载方案，在较大运力下仍然合法。所以候选运力从小到大的可行性一定是“不可行，然后可行”，可以二分寻找第一个可行值。

最小候选值是最重单件 max(weights)，否则这一件永远装不下；最大候选值是总重量 sum(weights)，它能在一天内运完，一定可行。二分始终把答案保留在闭区间 [left, right]：mid 可行时令 right = mid，不可行时令 left = mid + 1。

解题步骤

  1. 扫描包裹，得到最重单件和总重量，分别作为二分左右边界。
  2. 当 left < right 时，取中点 mid，模拟该运力下的运输过程。
  3. 模拟从 usedDays = 1、load = 0 开始。若 load + weight > mid，天数加一并清空当天载重；随后仍要把当前包裹计入新一天。
  4. 一旦天数超过 days 就返回不可行；全部包裹装完且未超时则可行。下界已保证每件包裹都能单独装下。
  5. 可行时保留 mid 并缩小右边界，不可行时排除 mid 及更小的运力。边界重合后，返回唯一剩下的最小可行运力。

代码实现

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
}

复杂度分析

设包裹数为 n，候选运力数为 R = sum(weights) - max(weights) + 1。

  • 时间复杂度：$O(n\log(R+1))$。初始扫描为 $O(n)$，每次可行性判断最多扫描全部包裹，二分次数为 $O(\log R)$；写作 $\log(R+1)$ 也覆盖只有一个候选值的情况。
  • 空间复杂度：$O(1)$，只维护二分边界、已用天数和当天载重。

关键点总结

[!green]

  • 固定运力时，按顺序尽量装满每天，得到这个运力能达到的最少天数。
  • 运力增大不会使原有方案失效，二分查找的是第一个可行值。
  • 最重单件保证模拟时任何包裹都能装下，总重量保证右边界始终存在可行答案。

易错点总结

[!yellow]

  • 先排序包裹：会改变必须保留的运输顺序。
  • 正好达到容量就换日：允许当天载重等于容量，只有严格超出时才换日。
  • 换日后跳过当前包裹：它只是当天放不下，仍需装入新的一天。
  • 要求恰好使用 days 天：题目要求在这些天内完成，更早运完同样可行。
  • 可行时令 right = mid - 1：会排除可能正是答案的 mid；不可行时则必须令 left = mid + 1，保证区间继续缩小。

相似题目

题目 难度 关联与区别
410. 分割数组的最大值 困难 同样按原顺序切分成有限个连续段，并二分最小可行的段和上限。
875. 爱吃香蕉的珂珂 中等 同样用候选能力值计算需要多少天或小时，利用单调性二分最小能力。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/83757472
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！