1011. 在 D 天内送达包裹的能力 #
- 标签:数组、二分查找
- 难度:中等
题目大意 #
描述:传送带上的包裹必须在 D
天内从一个港口运送到另一个港口。给定所有包裹的重量数组 weights
,货物必须按照给定的顺序装运。且每天船上装载的重量不会超过船的最大运载重量。
要求:求能在 D
天内将所有包裹送达的船的最低运载量。
说明:
- $1 \le days \le weights.length \le 5 * 10^4$。
- $1 \le weights[i] \le 500$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:二分查找 #
船最小的运载能力,最少也要等于或大于最重的那件包裹,即 max(weights)
。最多的话,可以一次性将所有包裹运完,即 sum(weights)
。船的运载能力介于 [max(weights), sum(weights)]
之间。
我们现在要做的就是从这个区间内,找到满足可以在 D
天内运送完所有包裹的最小载重量。
可以通过二分查找的方式,找到满足要求的最小载重量。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(\log_2 n)$。二分查找算法的时间复杂度为 $O(\log_2 n)$。
- 空间复杂度:$O(1)$。只用到了常数空间存放若干变量。