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

题目链接：1011. 在 D 天内送达包裹的能力

题目描述

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

核心思考：对能力值域进行二分查找

这道题在结构和思想上与 875. 爱吃香蕉的珂珂 十分相似。遇到这类限制天数或时间，求最小能力的题目，解题的关键在于明确以下三个核心要素：

1. 可变变量（搜索对象）：船的运载能力。
2. 评价指标（约束条件）：在给定运载能力下，搬运完所有货物所需的总天数。
3. 单调区间：运载能力越大，所需的天数越少。这构成了单调递减的关系，满足使用二分查找的前提。

确定二分查找边界

在进行二分查找前，我们需要确定运载能力的合理上下界：

• 最小运载能力（左边界 left）：由于包裹不能拆分运送，船的运载能力至少要能装下最重的那一个包裹。因此，左边界为 max(weights)。
• 最大运载能力（右边界 right）：最理想的情况是一次性将所有包裹全部运走。因此，右边界为所有包裹重量的总和 sum(weights)。

查找逻辑

在明确了 [max(weights), sum(weights)] 这个闭区间后，我们就可以通过二分查找不断测试当前的运载能力 mid：

• 若在运载能力为 mid 的情况下，所需天数 curr_days 大于规定的 days，说明当前能力不足，必须提高运载能力，将左边界更新为 left = mid + 1。
• 若所需天数 curr_days 小于或等于规定的 days，说明运载能力足够，但可能存在更小的满足条件的值。为了寻找“最低运载能力”，需要向左收缩查找区间，将右边界更新为 right = mid - 1。

当循环结束时，left 指针所在的数值即为满足条件的最低运载能力。

解题思路 (Python)

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # 在当前运载能力下所需要的天数
        def curr_power(weights,x):
            curr_weight = 0
            days = 1
            for i in weights:
                curr_weight += i
                if curr_weight > x:
                    days += 1
                    curr_weight = i
            return days
        # 该天数和给出的天数进行对比，如果小于给定天数说明搬运能力过强。
        # 大于则说明搬运能力需要提升
        # 要最左侧的搬运能力
        # 最小运载能力是最大货物，最大运载能力是一趟全搬走
        left = max(weights)
        right = sum(weights)

        while left <= right:
            mid = left + (right - left) // 2
            curr_days = curr_power(weights,mid)
            if curr_days > days:
                left = mid + 1
            else:
                right = mid - 1
        return left

复杂度分析

• 时间复杂度：$O(N \log(\Sigma W))$，其中 $N$ 是数组 weights 的长度，$\Sigma W$ 是数组中所有重量的总和。找出左右边界需要 $O(N)$ 的时间。二分查找的区间大小为 $\Sigma W$，最多进行 $O(\log(\Sigma W))$ 次迭代。在每一次查找中，调用 curr_power 函数需要遍历一次数组，耗时 $O(N)$。因此总时间复杂度为外层迭代次数与内层遍历的时间之积。
• 空间复杂度：$O(1)$。代码只使用了几个整型变量来记录边界和状态参数，并未分配与输入数据规模挂钩的额外空间。