车队 II

标签: 栈 数组 数学 单调栈 堆（优先队列）

难度: Hard

在一条单车道上有 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 <= 105
  • 1 <= positioni, speedi <= 106
  • positioni < positioni+1

Submission

运行时间: 298 ms

内存: 49.9 MB

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:

        n = len(cars)
        ans = [-1.0] * n
        stack = [] # 单调栈，栈底：车速更慢，且初始位置更靠右

        for i in range(n-1, -1, -1): # 从右往左遍历
            pos, speed = cars[i]

            # 弹出栈顶速度更快的车辆，直到栈顶车的速度小于当前车辆
            while stack and speed <= cars[stack[-1]][1]:
                stack.pop()

            # 从栈顶往栈底依次检查当前车是否能及时追上目标车辆
            while stack:
                j = stack[-1]
                time = (cars[j][0] - pos) / (speed - cars[j][1])
                if ans[j] < 0 or time <= ans[j]: # 若及时追上了，此即为解
                    ans[i] = time
                    break 
                stack.pop() # 否则弹出栈顶这辆已经检查过的车，准备看下一辆

            stack.append(i) # 此时当前车辆的速度一定大于栈顶的车辆，需入栈

        return ans

Explain

题解采用了单调栈的方法从右向左遍历车辆数组，通过比较速度和位置关系计算车辆相遇时间。具体来说，对于每一辆车，先将速度比当前车快或相等的车从栈中移除，这是因为这些车会比当前车先远离，难以相遇。接下来计算当前车与栈中车辆的相遇时间，如果当前车在相遇时间内能追上前车，且这个时间不晚于前车的相遇时间（如果有的话），则当前车的相遇时间就是这个时间。此后，将当前车加入栈中，因为可能有后面的车需要与之比较。这样一来，每辆车的计算都依赖于它前面的车的状态，通过栈来维持这种依赖关系，使得问题得以有效解决。

时间复杂度: O(n)

空间复杂度: O(n)

# 定义Solution类
class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        n = len(cars) # 车辆数量
        ans = [-1.0] * n # 初始化答案数组
        stack = [] # 单调栈

        # 从右到左遍历车辆
        for i in range(n-1, -1, -1):
            pos, speed = cars[i] # 当前车的位置和速度

            # 清理栈顶速度不低于当前车的车辆
            while stack and speed <= cars[stack[-1]][1]:
                stack.pop()

            # 计算当前车与栈中车辆的相遇时间
            while stack:
                j = stack[-1]
                time = (cars[j][0] - pos) / (speed - cars[j][1]) # 相遇时间
                if ans[j] < 0 or time <= ans[j]: # 如果当前车可以在前车相遇前追上前车
                    ans[i] = time
                    break
                stack.pop() # 否则继续考虑栈中下一辆车

            stack.append(i) # 将当前车辆索引压入栈中

        return ans # 返回结果

Explore

在栈中移除速度不低于当前车的车辆是因为，如果后面的车速度不超过前面的车，那么后面的车不可能追上前面的车，因而他们之间不可能相遇。根据速度的相对关系，只有当后车的速度高于前车时，后车才有可能在未来某个时刻追上前车。因此，如果栈顶车辆的速度大于等于当前车辆的速度，这意味着当前车辆永远追不上栈顶的车辆，所以可以将这样的车辆从栈中移除。

如果当前车的速度比所有栈中车辆都慢，那么该车不可能追上任何前面的车辆。因为追上前车的基本条件是后车速度必须大于前车。数学上，如果车i的速度小于车j的速度（车j在车i前面），那么相遇时间计算为 `(pos_j - pos_i) / (speed_i - speed_j)`。由于 `speed_i < speed_j`，分母为负，此时相遇时间计算结果将是一个负数，这在物理意义上表示车i在过去已经被车j超过。因此，当没有任何车的速度比当前车慢时，当前车的答案直接设为 `-1.0`，表示永远不会有相遇发生。

单调栈在这个问题中用于维持一个车辆索引的序列，其中每辆车的速度都严格小于前一辆车的速度。这种结构使得对于任何新车辆，我们能快速地通过栈顶向下比较找到第一辆可能会相遇的车辆。选择从右向左遍历车辆数组是因为这样可以逐步构建出每辆车的相遇时间。如果从左向右遍历，则前面车辆的相遇信息尚未计算完成，就无法为后续车辆提供必要的信息，从而无法正确计算相遇时间。从右到左遍历确保我们在处理每辆车时，其相遇可能发生的所有“前车”信息已经就绪且存储在栈中。