题目

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

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

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

示例 1:

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

思路与算法

假设当船的运载能力为 x 时，可以在 D 天内运送完所有包裹

• 运载能力大于 x，同样可以在 D 天内运送完所有包裹
• 运载能力小于 x，无法在 D 天内运送完所有包裹

这样一来，就跟在已经排序的数组内，寻找某个能区分两个区域界限的特殊值的情况一致了
因此可以使用二分法寻找这个特殊值

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def is_can_handle(machine_power: int) -> bool:
            sum_weight, spend_day = 0, 1
            for weight in weights:
                if sum_weight + weight > machine_power:
                    spend_day += 1
                    sum_weight = 0
                sum_weight += weight
            return spend_day <= D

        left = max(weights)
        right = left * len(weights)

        while left < right:
            avg_machine_power = (left + right) // 2
            if is_can_handle(avg_machine_power):
                right = avg_machine_power
            else:
                left = avg_machine_power + 1
        return left

复杂度分析

时间复杂度：O(nlog(Σw))，其中 n 是数组 weights 的长度，Σw 是数组 weights 中元素的和。二分查找需要执行的次数为 O(log(Σw))，每一步中需要对数组 weights 进行依次遍历，时间为 O(n)，相乘即可得到总时间复杂度

空间复杂度：O(1)

---

参考：

• https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution/zai-d-tian-nei-song-da-bao-guo-de-neng-l-ntml/