各位题友大家好！今天是 @负雪明烛 坚持日更的第 87 天。今天力扣上的每日一题是「1011. 在 D 天内送达包裹的能力」。

解题思路

题意：给出了一个数组 weights，给出了一个数字 D，求满足最小的承载量的船，能让 weights 在最多 D 天内全部运走。需要注意的是不能交换 weights 中的顺序。

思路：题目要求船的最小承载量，我们就把船的承载量作为变量。遍历所有可行的船的承载量，找出最小承载量。

船的承载量有范围要求的，首先，由于货物不能拆分，所以船的承载量必须大于等于货物中的最大重量；其次，如果船的承载量大于等于所有货物的重量之和，那么所有货物可以在一天时间内全部拉走，所以船的承载量一定会小于等于所有货物的重量之和。故 max(weights) <= 船的承载量 <= sum(weights)。

找出船的承载量范围之后，我们思考怎么寻找能在 D 天内能把所有货物都拉走的最小承载量。对于船的承载量为 x 时，由于必须按顺序装载 weights ，所以依次遍历 weights，尽可能能装更多的货，直到这一船装不下了新的货物；从而来计算需要多少天能把所有货物拉完。对于每个 x 计算货物拉完的天数时，需要把所有的 weights 遍历一遍，时间复杂度是 $O(weights)$。

那么怎么寻找最小的船承载量 x 呢？上面我们已经分析了 max(weights) <= 船的承载量 <= sum(weights)，如果在这个区间内逐一遍历并判断肯定是不可以的，那样的时间复杂度会过高。肯定会超时。

我们发现这不就是个查找问题么？在指定空间内，查找满足一定条件的解。我们可以用二分查找！

分享二分查找的模板：

public int search(int[] nums, int left, int right, int target) {
    while (left < right) {
        // 选择中位数时下取整
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            // 下一轮搜索区间是 [mid + 1, right]
            left = mid + 1
        } else {
            // 下一轮搜索区间是 [left, mid]
            right = mid
        }
    }
    // 退出循环的时候，程序只剩下一个元素没有看到。
    // 视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
}

这个题目，其实就把上面的 check(mid)换成当船的承载量是 mid 时，能否在 D 天内运走所有的货物。

至此，思路已经非常明白了，代码如下。

class Solution(object):
    def shipWithinDays(self, weights, D):
        l = max(weights)
        r = sum(weights)
        # [l, r)
        while l < r:
            mid = l + (r - l) / 2
            if self.getNeedDays(weights, mid) > D:
                l = mid + 1
            else:
                r = mid
        return l
    def getNeedDays(self, weights, x):
        need = 1
        cur = 0
        for w in weights:
            if cur + w > x:
                need += 1
                cur = 0
            cur += w
        return need

时间复杂度：$O(len(weights) * log(sum(weights)))$。
空间复杂度：$O(1)$。

刷题心得

二分查找，其实不单单是在一个有序数组上能用，要开拓思路。

参考资料：AlgoWiki

相似题目：
875. 爱吃香蕉的珂珂

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】1011. 在 D 天内送达包裹的能力

解题思路

刷题心得