LeetCode 题解工作台
车队 II
在一条单车道上有 n 辆车，它们朝着同样的方向行驶。给你一个长度为 n 的数组 cars ，其中 cars[i] = [position i , speed i ] ，它表示： position i 是第 i 辆车和道路起点之间的距离（单位：米）。题目保证 position i i+1 。 spee…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
由于每一辆车最终追上其右边第一辆车的时间与其左边的车没有关系，因此，我们可以从右往左遍历，计算每辆车与其右边第一辆车相遇的时间。 具体地，我们维护一个栈，栈中存放的是车辆的编号，栈顶元素表示当前最慢的车辆编号，栈底元素表示当前最快的车辆编号。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
在一条单车道上有 n 辆车，它们朝着同样的方向行驶。给你一个长度为 n 的数组 cars ，其中 cars[i] = [positioni, speedi] ，它表示：
positioni是第i辆车和道路起点之间的距离（单位：米）。题目保证positioni < positioni+1。speedi是第i辆车的初始速度（单位：米/秒）。
简单起见，所有车子可以视为在数轴上移动的点。当两辆车占据同一个位置时，我们称它们相遇了。一旦两辆车相遇，它们会合并成一个车队，这个车队里的车有着同样的位置和相同的速度，速度为这个车队里 最慢 一辆车的速度。
请你返回一个数组 answer ，其中 answer[i] 是第 i 辆车与下一辆车相遇的时间（单位：秒），如果这辆车不会与下一辆车相遇，则 answer[i] 为 -1 。答案精度误差需在 10-5 以内。
示例 1：
输入：cars = [[1,2],[2,1],[4,3],[7,2]] 输出：[1.00000,-1.00000,3.00000,-1.00000] 解释：经过恰好 1 秒以后，第一辆车会与第二辆车相遇，并形成一个 1 m/s 的车队。经过恰好 3 秒以后，第三辆车会与第四辆车相遇，并形成一个 2 m/s 的车队。
示例 2：
输入：cars = [[3,4],[5,4],[6,3],[9,1]] 输出：[2.00000,1.00000,1.50000,-1.00000]
提示：
1 <= cars.length <= 1051 <= positioni, speedi <= 106positioni < positioni+1
解题思路
方法一：栈
由于每一辆车最终追上其右边第一辆车的时间与其左边的车没有关系，因此，我们可以从右往左遍历，计算每辆车与其右边第一辆车相遇的时间。
具体地，我们维护一个栈，栈中存放的是车辆的编号，栈顶元素表示当前最慢的车辆编号，栈底元素表示当前最快的车辆编号。
当我们遍历到第 辆车时，如果第 辆车的速度大于栈顶元素对应的车辆 的速度，此时我们计算两车相遇的时间，记为 。如果车辆 与右边车辆不会相遇，或者 小于等于 与右辆车相遇的时间，说明车辆 可以在 时间追上车辆 ，更新答案。否则，说明车辆 不会与车辆 相遇，我们将车辆 出栈，继续判断车辆 与栈顶元素对应的车辆相遇的时间。如果栈为空，说明车辆 不会与任何车辆相遇，更新答案为 。最后，将车辆 入栈。
遍历完所有车辆后，即可得到答案。
时间复杂度 ，空间复杂度 。其中 为车辆数量。
class Solution:
def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
stk = []
n = len(cars)
ans = [-1] * n
for i in range(n - 1, -1, -1):
while stk:
j = stk[-1]
if cars[i][1] > cars[j][1]:
t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])
if ans[j] == -1 or t <= ans[j]:
ans[i] = t
break
stk.pop()
stk.append(i)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding the stack-based state management is key to solving this problem.
- question_mark
Candidates should demonstrate familiarity with simulating car fleets efficiently.
- question_mark
Be aware of the subtle handling of edge cases such as cars not colliding.
常见陷阱
外企场景- error
Failing to handle the case where a car’s speed is greater than the next car’s speed, resulting in no collision.
- error
Incorrectly merging fleets or failing to track fleet speeds properly.
- error
Forgetting to handle the case where no collision happens (returning -1).
进阶变体
外企场景- arrow_right_alt
What if the cars were moving in different directions?
- arrow_right_alt
How would the problem change if you were asked to track the position of each car over time?
- arrow_right_alt
What if there were additional constraints like fuel limits on each car?