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

Categories:

题目描述
思路分析
1. 解法一：二分答案（推荐）
相似题目

题目描述

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

思路分析

解法一：二分答案（推荐）

核心思路：

运输能力越大，所需天数越少，具有单调性。

二分能力 cap，用贪心计算所需天数。

找到最小可行能力。

复杂度分析：

时间复杂度：O(n log S)，其中 n 为包裹数量，S 为总重量。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int 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, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canShip(int[] weights, int days, int cap) {
        int need = 1;
        int cur = 0;

        for (int w : weights) {
            if (cur + w > cap) {
                need++;
                cur = 0;
            }
            cur += w;
        }

        return need <= days;
    }
}

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

	// 二分最小可行能力
	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, cap int) bool {
	need := 1
	cur := 0
	for _, w := range weights {
		if cur+w > cap {
			need++
			cur = 0
		}
		cur += w
	}
	return need <= days
}

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	二分答案
410. 分割数组的最大值	困难	二分答案
1011. 在 D 天内送达包裹的能力	中等	二分答案
1482. 制作 m 束花所需的最少天数	中等	二分答案
2064. 分配给商店的最多商品的最小值	中等	二分答案

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/83757472