题目描述
思路解析
一句话答案：LeetCode 1870 准时到达的列车最小时速用二分答案：时速越大总用时越短这条单调性，让判定函数（前 n-1 趟向上取整、末趟不取整再求和 ≤hour）能二分出最小可行时速，时间 O(n·log C)、空间 O(1)。
n 趟车按顺序坐完，这题求的是哪个时速
给一个浮点数 hour 和长度 n 的整数数组 dist（dist[i] 是第 i 趟距离）。以整数时速 v 依次坐完 n 趟，第 i 趟纯行驶 dist[i]÷v 小时；列车只整点发车，前 n-1 趟到站没到整点得等下个整点才能换乘，末趟到公司就结束。求能准时（总用时 ≤hour）的最小整数时速，来不及返回 -1。题面 dist=[1,3,2]、hour=2.7 答案 3。
从时速 1 一档档往上试，慢在哪
时速最小 1、上界题目保证不超过 1e7。直接办法是从 1 起每个时速试一遍，把 n 趟用时加起来看超不超 hour，第一个不超的即答案。可最坏要试到上界，试的次数和整个值域（所有可能的时速，从 1 到某上限）一样多，是 O(C)；C 到 1e7 就试不动了。
时速和能否准时之间，卡着一条单调界线
把每个时速的总用时排一排：时速越大每趟越快，前面向上取整的项要么不变要么变小、末趟也变小，总用时只减不增——这是单调（只朝一个方向走）。于是时速切成两段，慢的都超时、快的都准时，答案是界线上第一个够快的时速，二分就能逼近它。这里二分的不是下标，是时速这个答案值本身；不直接算、猜一个值再验证行不行，叫二分答案。
判定一个时速够不够快，函数怎么写
把「行不行」做成判定函数 check(v)：遍历 dist，前 n-1 趟每趟加 ceil(dist[i]÷v)（ceil 即向上取整，对应到站没赶上整点、得等下一班），末趟加 dist[last]÷v 不取整（终点是公司、没车要赶）。累加后 ≤hour 就够快。二分取中点 mid：check 为真、mid 够快就 hi=mid，为假太慢就 lo=mid+1，缩到 lo、hi 撞上就是答案。
拿 dist=[1,3,2]、hour=2.7 逐轮验时速
把上界收到演示窗口 16 看清每步。lo=1、hi=16。第一轮 mid=8：ceil(1/8)=1、ceil(3/8)=1、末趟 2/8=0.25，合计 2.25 ≤2.7 够快，hi=8。第二轮 mid=4：1、1、2/4=0.5，合计 2.5，hi=4。第三轮 mid=2：1、ceil(3/2)=2、2/2=1，合计 4 >2.7 太慢，lo=3。第四轮 mid=3：1、1、2/3≈0.667，合计 2.667 ≤2.7，hi=3。lo=hi=3，返回 3。
本来够快的时速，怎么会被判成来不及
最容易错的是把末趟也向上取整：整点发车只约束换乘，末趟到公司就结束、没下一班要赶，把它取整会多算一段等待，能准时的时速被误判成来不及、答案偏大。其次二分的是时速值、不是数组下标；开头还得先过不可能闸——前 n-1 趟每趟至少占 1 个整点，总用时压不到 n-1 及以下，代码用 n > ceil(hour) 判死，hour=1.9 时 ceil=2、n=3 就返回 -1。
复杂度 O(n·log C)（二分 log C 轮、每轮扫 n 趟），空间 O(1)。收缩别写反：够快 hi=mid、太慢 lo=mid+1；写成 hi=mid-1 会丢答案，写成 lo=mid 只剩两档时会死循环。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:时速越大用时越短,可行性单调,于是二分时速 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题