LeetCode 题解工作台
准时到达的列车最小时速
给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。 每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。 例如，…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们注意到，如果一个速度值 能够使得我们在规定时间内到达，那么对于任意 $v' > v$，我们也一定能在规定时间内到达。这存在着单调性，因此我们可以使用二分查找，找到最小的满足条件的速度值。 在二分查找之前，我们需要先判断是否有可能在规定时间内到达。如果列车数量大于向上取整的规定时间，那么一定无法在规定时间内到达，直接返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。
- 例如，第
1趟列车需要1.5小时，那你必须再等待0.5小时，搭乘在第 2 小时发车的第2趟列车。
返回能满足你在时限前到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。
生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。
示例 1：
输入：dist = [1,3,2], hour = 6 输出：1 解释：速度为 1 时： - 第 1 趟列车运行需要 1/1 = 1 小时。 - 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。 - 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。 - 你将会恰好在第 6 小时到达。
示例 2：
输入：dist = [1,3,2], hour = 2.7 输出：3 解释：速度为 3 时： - 第 1 趟列车运行需要 1/3 = 0.33333 小时。 - 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。 - 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。 - 你将会在第 2.66667 小时到达。
示例 3：
输入：dist = [1,3,2], hour = 1.9 输出：-1 解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。
提示：
n == dist.length1 <= n <= 1051 <= dist[i] <= 1051 <= hour <= 109hours中，小数点后最多存在两位数字
解题思路
方法一：二分查找
我们注意到，如果一个速度值 能够使得我们在规定时间内到达，那么对于任意 ，我们也一定能在规定时间内到达。这存在着单调性，因此我们可以使用二分查找，找到最小的满足条件的速度值。
在二分查找之前，我们需要先判断是否有可能在规定时间内到达。如果列车数量大于向上取整的规定时间，那么一定无法在规定时间内到达，直接返回 。
接下来，我们定义二分的左右边界为 , ，然后我们每次取中间值 ，判断是否满足条件。如果满足条件，我们将右边界移动到 ，否则将左边界移动到 。
问题转化为判断一个速度值 是否能够在规定时间内到达。我们可以遍历每一趟列车，计算每一趟列车的运行时间 ，如果是最后一趟列车，我们直接加上 ，否则我们向上取整加上 。最后判断总时间是否小于等于规定时间，如果是则说明满足条件。
二分结束后，如果左边界超过了 ，说明无法在规定时间内到达，返回 ，否则返回左边界。
时间复杂度 ，其中 和 分别为列车数量和速度的上界。空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should show comfort with binary search, applying it to a non-trivial range (speed).
- question_mark
The candidate should be able to clearly explain how to handle integer hour restrictions and waiting times.
- question_mark
Expect clarity in distinguishing between calculating travel time and handling edge cases where the trip cannot be completed on time.
常见陷阱
外企场景- error
Overlooking the waiting time between train rides when calculating travel times.
- error
Not correctly adjusting for the fact that you can only depart at integer hours.
- error
Incorrect binary search bounds or failure to optimize the range for speed effectively.
进阶变体
外企场景- arrow_right_alt
Increase the difficulty by adding more complex conditions, like varying speeds or multiple constraints on time.
- arrow_right_alt
Modify the problem to consider alternative transportation methods or constraints that could affect the time.
- arrow_right_alt
Extend the problem to consider dynamic changes in speed or delays during travel.