LC1011
在 D 天内送达包裹的能力
二分答案 · 船运可视化:答案二分weights 分 d 天运完,最小船载重 capacity。
时间 O(n)空间 O(1)
题目1 / 10
题目与输入建立输入、目标与算法心智
判定:cap 下能否在 days 天内运完
正在加载算法场景...
当前发生了什么
weights 分 d 天运完,最小船载重 capacity。
机器状态
lo/hi capacity、days 验证。
为什么正确
二分 capacity,贪心看需几天(超则天+1)。
不变量
验证随 capacity 增大 days 减少。
面试怎么说
二分+贪心 O(n log sum)。
人类输入
weights 分 d 天运完,最小船载重 capacity。
机制
二分 capacity,贪心看需几天(超则天+1)。
机器状态
lo/hi capacity、days 验证。
可观察结果
最小 capacity。
不变量
- · 验证随 capacity 增大 days 减少。
常见误区
- · 贪心装船:当前超重开新的一天。
迁移练习
- · LC875
- · LC410
面试怎么答
二分+贪心 O(n log sum)。