题目描述
思路解析动画文字版
记牢:时速越大用时越短,可行性单调,于是二分时速 v。检查一个 v:前 n-1 趟用时 ceil(dist[i]/v)、最后一趟不取整,求和 ≤ hour 则可行、收紧右界,否则抬高左界。先过不可能闸 n 大于 ceil(hour) 返回 -1。二分的是时速值,不是下标。
总览 · 三趟车要在 2.7 小时内跑完：先看清画面。上面这排格子是三趟列车的距离 1、3、2,你要按这个顺序依次坐完,总时间只有 2.7 小时。右边面板记三件事:时速的候选范围、当前正在检验的时速 v、以及这个 v 下的累计用时,现在都还没开始。思路不是硬凑时速,而是二分猜一个时速 v,再验证它够不够快。
不可能闸 · n 是否大于 ceil(hour)：开二分前先过一道快速闸。前 n-1 趟每趟至少要占 1 个整点,加上最后一趟,哪怕时速无穷大,总用时也压不到 n-1 小时以下。所以只要趟数 n 大于 ceil(hour),就说明再快也排不进这点时间,直接返回 -1。这里 n 是 3,ceil(2.7) 是 3,3 并不大于 3,闸通过,可以放心去二分找答案。
定范围 · 在 1 到 16 上二分时速：框定答案的范围。时速最小是 1,再慢就不是正整数了。上界方面,参考代码直接用题目保证的 1e7,这里为了让每一步都看得清,把演示窗口缩到 16,机制完全一样。接下来不逐个试,而是二分:取范围中点当候选时速 v,验证这个 v 够不够准时。请记住,右边面板里动的是时速 v 的范围,数组这排列车始终不动。
第一轮 · 取中点 v = 8：开始第一轮二分。当前范围是 1 到 16,取中点得候选时速 v 等于 8。也就是先问:以时速 8 开,总用时能不超过 2.7 小时吗?下面逐趟算它的用时,把它们累加起来,再和 2.7 比。
第一轮 · 第 0 趟(距离 1)：看第 0 趟,距离 1。纯行驶时间是 1 除以 8 等于 0.125 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
第一轮 · 第 1 趟(距离 3)：看第 1 趟,距离 3。纯行驶时间是 3 除以 8 等于 0.375 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 2。
第一轮 · 第 2 趟(距离 2) · 末趟：看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 8 等于 0.25。把它加进累计用时,现在合计 2.25 小时,这就是时速 8 下的总用时。
第一轮 · v = 8 能准时：三趟车算完,总用时 2.25 小时,不超过 2.7,说明时速 8 能准时到达。既然 8 就够了,那更快的时速就不用看了,把右界收到 8,范围变成 1 到 8。注意 8 本身可能就是最小答案,所以右界取 8 而不是 8 减 1,继续往更慢里试。
第二轮 · 取中点 v = 4：第二轮二分。上一轮把范围收到了 [1, 8],取中点得候选时速 v 等于 4。同样地问一句:时速 4 够快能准时吗?逐趟算用时、累加、再和 2.7 比。
第二轮 · 第 0 趟(距离 1)：看第 0 趟,距离 1。纯行驶时间是 1 除以 4 等于 0.25 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
第二轮 · 第 1 趟(距离 3)：看第 1 趟,距离 3。纯行驶时间是 3 除以 4 等于 0.75 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 2。
第二轮 · 第 2 趟(距离 2) · 末趟：看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 4 等于 0.5。把它加进累计用时,现在合计 2.5 小时,这就是时速 4 下的总用时。
第二轮 · v = 4 能准时：三趟车算完,总用时 2.5 小时,不超过 2.7,说明时速 4 能准时到达。既然 4 就够了,那更快的时速就不用看了,把右界收到 4,范围变成 1 到 4。注意 4 本身可能就是最小答案,所以右界取 4 而不是 4 减 1,继续往更慢里试。
第三轮 · 取中点 v = 2：第三轮二分。上一轮把范围收到了 [1, 4],取中点得候选时速 v 等于 2。同样地问一句:时速 2 够快能准时吗?逐趟算用时、累加、再和 2.7 比。
第三轮 · 第 0 趟(距离 1)：看第 0 趟,距离 1。纯行驶时间是 1 除以 2 等于 0.5 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
第三轮 · 第 1 趟(距离 3)：看第 1 趟,距离 3。纯行驶时间是 3 除以 2 等于 1.5 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 2 小时。累计用时来到 3。
第三轮 · 第 2 趟(距离 2) · 末趟：看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 2 等于 1。把它加进累计用时,现在合计 4 小时,这就是时速 2 下的总用时。
第三轮 · v = 2 来不及：三趟车算完,总用时 4 小时,超过了 2.7,说明时速 2 太慢、赶不上。那 2 以及更慢的都不行,把左界抬到 3,范围变成 3 到 4,接着往更快里找。
第四轮 · 取中点 v = 3：第四轮二分。上一轮把范围收到了 [3, 4],取中点得候选时速 v 等于 3。同样地问一句:时速 3 够快能准时吗?逐趟算用时、累加、再和 2.7 比。
第四轮 · 第 0 趟(距离 1)：看第 0 趟,距离 1。纯行驶时间是 1 除以 3 等于 0.333 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
第四轮 · 第 1 趟(距离 3)：看第 1 趟,距离 3。纯行驶时间是 3 除以 3 等于 1 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 2。
第四轮 · 第 2 趟(距离 2) · 末趟：看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 3 等于 0.667。把它加进累计用时,现在合计 2.667 小时,这就是时速 3 下的总用时。
第四轮 · v = 3 能准时：三趟车算完,总用时 2.667 小时,不超过 2.7,说明时速 3 能准时到达。既然 3 就够了,那更快的时速就不用看了,把右界收到 3,范围变成 3 到 3,此时左界和右界已经相等,二分结束,答案候选锁定为 3。
收束 · 左右界重合于 3：二分收束了。左界和右界都停在 3,说明 3 是能准时到达的最小时速:它可行,而比它慢的 2 已经验证过来不及。回看时速 3 那一轮,前两趟各取整成 1 小时,最后一趟 2 除以 3 约等于 0.667 小时不取整,合计约 2.667 小时,刚好卡在 2.7 以内。
完成 · 最小时速 = 3：收个尾。整道题的巧劲在于把「最小时速是多少」这个难题,翻译成「时速 v 够不够准时」这个好答的判断题,再靠单调性二分时速。dist = 1,3,2、hour = 2.7,我们只检验了 8、4、2、3 这几个候选时速,就锁定最小时速是 3。可行性检查里那句「前面取整、末趟不取整」,正是整点发车规则的精确翻译,千万别把最后一趟也取整了。
边界:dist=1,3,2、hour=6 时速 1 合计恰好 6 准时;hour=1.9 时 n=3 大于 ceil(1.9)=2 被不可能闸拦下返回 -1;dist=2,3,1、hour=5 最小时速 2(时速 1 合计 6 超时)。
面试重点:时速越大用时越短,可行性单调所以能二分;最后一趟没有要赶的车所以不取整;难点是自己设计可行性判定,把求最优翻译成判定「时速够不够快」,范围取 1 到上界、开头先过不可能闸。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minSpeedOnTime(self, dist: List[int], hour: float) -> int: def check(v: int) -> bool: s = 0 for i, d in enumerate(dist): t = d / v s += t if i == len(dist) - 1 else ceil(t) return s <= hour if len(dist) > ceil(hour): return -1 r = 10**7 + 1 ans = bisect_left(range(1, r), True, key=check) + 1 return -1 if ans == r else ans复杂度
- 时间：O(n log C)，n 是列车趟数,C 是时速上界(参考代码取 1e7)。二分在时速范围上进行,最多 log C 轮;每一轮做一次可行性检查,要扫一遍全部 n 趟车累加用时,是 O(n)。两者相乘就是 O(n log C)。演示里 n 等于 3,只检验了 4 个候选时速就收敛
- 空间：O(1)，按峰值算。除了输入数组,只用了 l、r、mid 和一个累加用时的变量,都是常数个标量,不随规模增长。Python 里的 range 是惰性对象、不真的展开成数组,bisect 也只用常数额外空间。全程没有开新数组,所以额外空间是常数 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么时速可以拿来二分?单调性到底体现在哪?
追问为什么偏偏最后一趟不向上取整?
追问和普通的「在有序数组里二分找目标」比,这题难在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
可移除字符的最大数目
LeetCode 1898 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题