跳至主要內容

D 天内送达包裹：二分答案工业级应用

老张2026/4/30大约 7 分钟

D 天内送达包裹：二分答案工业级应用

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 16 分钟 | 难度：⭐⭐⭐

开篇故事

LeetCode 1011 和上一篇讲的珂珂吃香蕉（875）几乎是孪生兄弟。我第一次做这道题时，只花了不到五分钟——因为刚刚做完 875，脑子里模板还热乎着，直接套用，一遍过。

但这道题有一些工业级的细节值得深挖，比如答案空间的边界怎么确定、验证函数中的贪心策略、以及这个模式在真实工程中的应用场景。

在工作中，我曾经遇到过一个任务调度优化问题：给定一批任务，每个任务有处理时间，问如何分配到 k 台服务器上，使得所有服务器的最大负载最小化。这其实就是 LeetCode 410（分割数组的最大值）的变体，而它的解法核心和 1011 完全一样。二分答案这个思路，在工程实践里比很多人想象的更有用。

一、题目解析

题目（LeetCode 1011）： 传送带上有一批包裹，第 i 个包裹的重量为 weights[i]。每天可以按顺序装载包裹（不可打乱顺序），船的日载重量上限为 capacity。找到在 days 天内把所有包裹送走所需的最低日载重量。

示例：

  • weights = [1,2,3,4,5,6,7,8,9,10]，days = 5，输出：15
  • weights = [3,2,2,4,1,4]，days = 3，输出：6

关键约束：

  • 包裹必须按顺序装载（不能跳过），所以不是背包问题，而是分割子数组问题。
  • 答案空间：
    • 下界 = max(weights)：至少要能装下最重的那个包裹。
    • 上界 = sum(weights)：一天装完所有包裹的极限情况。
  • 单调性：capacity 越大，所需天数越少或相等，单调不增。

二、解法一：暴力枚举（O(n * sum(weights))）

public class Solution1 {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = Math.max(lo, w);  // 下界
            hi += w;               // 上界
        }

        for (int cap = lo; cap <= hi; cap++) {
            if (canShip(weights, cap, days)) {
                return cap;
            }
        }
        return hi;
    }

    private boolean canShip(int[] weights, int cap, int days) {
        int daysUsed = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > cap) {
                daysUsed++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return daysUsed <= days;
    }
}

复杂度分析

  • 时间复杂度：O(n * sum(weights))。不可接受。
  • 空间复杂度：O(1)。

三、解法二：二分答案（O(n log(sum))）

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

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

    private boolean canShip(int[] weights, int cap, int days) {
        int daysUsed = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > cap) {
                daysUsed++;
                currentLoad = 0;
                if (daysUsed > days) return false;  // 提前剪枝
            }
            currentLoad += w;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution2 sol = new Solution2();
        System.out.println(sol.shipWithinDays(
                new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // 15
        System.out.println(sol.shipWithinDays(
                new int[]{3,2,2,4,1,4}, 3)); // 6
        System.out.println(sol.shipWithinDays(
                new int[]{1,2,3,1,1}, 4)); // 3
    }
}

复杂度分析

  • 时间复杂度：O(n log(sum(weights)))。sum 最大 510^4 * 500 = 2.510^7，log 约 25 次。
  • 空间复杂度：O(1)。

四、解法三最优：完整实现 + 与 LeetCode 410 对比

思路分析

这道题和 LeetCode 410（分割数组的最大值）几乎完全一样，区别只是：

  • 1011：固定 days，最小化 capacity。
  • 410：固定 m（组数），最小化最大子数组和。

两道题的二分框架和验证函数几乎相同，只是变量名不同。下面把两道题的代码放在一起，方便对比。

Mermaid 图：验证函数（贪心装载）流程

完整代码（含 LeetCode 410 对比）

public class Solution3 {
    /**
     * LeetCode 1011：D天内送达包裹（最低日载重量）
     */
    public int shipWithinDays(int[] weights, int days) {
        int left = maxOf(weights), right = sumOf(weights);

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

    // 以 cap 为日载重量，最少需要几天（贪心：能装就装，不能装就新开一天）
    private int daysNeeded(int[] weights, int cap) {
        int days = 1, load = 0;
        for (int w : weights) {
            if (load + w > cap) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days;
    }

    /**
     * LeetCode 410：分割数组的最大值（最小化最大子数组和）
     * 几乎完全一样的框架，m 对应 days，最大子数组和对应 capacity
     */
    public int splitArray(int[] nums, int m) {
        int left = maxOf(nums), right = sumOf(nums);

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (splitsNeeded(nums, mid) <= m) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private int splitsNeeded(int[] nums, int maxSum) {
        int parts = 1, sum = 0;
        for (int n : nums) {
            if (sum + n > maxSum) {
                parts++;
                sum = 0;
            }
            sum += n;
        }
        return parts;
    }

    private int maxOf(int[] arr) {
        int max = 0;
        for (int x : arr) max = Math.max(max, x);
        return max;
    }

    private int sumOf(int[] arr) {
        int sum = 0;
        for (int x : arr) sum += x;
        return sum;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();

        // LeetCode 1011
        System.out.println(sol.shipWithinDays(
                new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // 15
        System.out.println(sol.shipWithinDays(
                new int[]{3,2,2,4,1,4}, 3)); // 6

        // LeetCode 410
        System.out.println(sol.splitArray(new int[]{7,2,5,10,8}, 2)); // 18
        System.out.println(sol.splitArray(new int[]{1,2,3,4,5}, 2)); // 9
    }
}

复杂度分析

  • 时间复杂度：O(n log S)，S = sum(weights)。
  • 空间复杂度：O(1)。

五、举一反三：二分答案题目总览

题号题目答案下界答案上界验证函数
875爱吃香蕉的珂珂1max(piles)以速度 k 能否在 h 小时内吃完
1011D天内送达包裹max(w)sum(w)以容量 c 能否在 d 天内送完
410分割数组的最大值max(num)sum(num)以上限 m 能否分成不超过 k 段
1482制作 m 束花110^9第 day 天能否做 m 束花
1552两球之间的磁力1maxPos-minPos以最小间距 d 能否放 m 个球

工程场景中的二分答案：

在分布式系统中，任务调度、负载均衡、资源分配等场景大量用到二分答案的思想：

  • 找最小的机器数量，使每台机器的负载不超过某个阈值
  • 找最大的请求量，使系统响应时间不超过 SLA
  • 找最优的批次大小，在内存限制下最大化吞吐量

六、踩坑实录

坑一：答案下界设置错误

答案下界必须是 max(weights) 而不是 1。如果下界设为 1，二分就会探索很多无效的 capacity 值（比 max(weights) 小的值，根本无法装载最重的包裹），浪费大量计算，还可能引入奇怪的 bug。

坑二：验证函数里忘记更新 load

在贪心装载的验证函数里，新开一天时，除了 days++，还需要 load = 0，然后再 load += w。如果忘记 load = 0，当前包裹就丢失了，统计结果会错误。我在一次代码审查中发现同事犯了这个错，真的是很低级但很容易犯的错。

坑三：sum(weights) 溢出

weights[i] 最大为 500，数组最长为 510^4，sum 最大为 2.510^7，不超过 int 范围。但如果题目换成更大的数据，就需要用 long。保险起见，求和时可以用 long 累加。

坑四：把"最小化最大值"和"最大化最小值"的二分方向搞反

"最小化最大值"用 lowerBound 模板：找最小的满足条件的值，check(mid) 为 true 时 right = mid，为 false 时 left = mid + 1。

"最大化最小值"用 upperBound 变种：找最大的满足条件的值，check(mid) 为 true 时 left = mid，为 false 时 right = mid - 1，此时 mid = left + (right - left + 1) / 2 防死循环。

两种方向搞混了，结果就全错了。我专门用颜色标注在笔记里：红色是找最小，蓝色是找最大。

坑五：验证函数时间复杂度过高

有人在验证函数里用了 O(n²) 的逻辑，导致整体复杂度变成 O(n² log S)，超时。验证函数必须是 O(n) 的贪心扫描，不能用 DP 或嵌套循环。

七、总结

LeetCode 1011 是二分答案模板的最佳入门练习之一，因为它的答案空间和验证函数都非常直观：capacity 就是答案，贪心扫描就是验证。

与 LeetCode 875（珂珂吃香蕉）对比：

  • 875 的验证函数是"向上取整求和"，比较简单。
  • 1011 的验证函数是"贪心装载"，略复杂但也不难。

两道题的二分框架完全相同，练透这两道题，"二分答案"这个思路就真正掌握了。

记住这句话：当问题是"求最小/最大的 X 使某条件成立"时，先思考能不能用二分答案，这往往是最优解。

编辑此页
最近更新:
贡献者: xiaozhangge