Hard

题目描述

在一条单车道上有 n 辆车沿着同一个方向行驶，这些车的速度各不相同。给你一个长度为 n 的数组 cars，其中 cars[i] = [positioni, speedi] 表示：

  • positioni 是第 i 辆车与道路起点的距离（单位：米）。题目保证 positioni < positioni+1。
  • speedi 是第 i 辆车的初始速度（单位：米/秒）。

为了简单起见，汽车可以视为在数轴上移动的点。当两辆车占据相同位置时就会发生碰撞。一旦一辆车与另一辆车发生碰撞，它们就会合并形成一个车队。车队中的汽车将拥有相同的位置和相同的速度，即车队中最慢汽车的初始速度。

返回数组 answer，其中 answer[i] 是第 i 辆车与下一辆车发生碰撞的时间（秒），如果该车不会与下一辆车发生碰撞，则为 -1。与实际答案误差在 10^-5 以内的答案都可以接受。

示例 1：

输入：cars = [[1,2],[2,1],[4,3],[7,2]]
输出：[1.00000,-1.00000,3.00000,-1.00000]
解释：恰好经过1秒后，第一辆车将与第二辆车发生碰撞，形成一个速度为1米/秒的车队。恰好经过3秒后，第三辆车将与第四辆车发生碰撞，形成一个速度为2米/秒的车队。

示例 2：

输入：cars = [[3,4],[5,4],[6,3],[9,1]]
输出：[2.00000,1.00000,1.50000,-1.00000]

约束：

  • 1 <= cars.length <= 10^5
  • 1 <= positioni, speedi <= 10^6
  • positioni < positioni+1

解题思路

这道题的核心思想是使用单调栈来维护候选的碰撞目标车辆。

分析过程：

  1. 基本碰撞条件：车 i 能追上车 j（i < j）的条件是 speed[i] > speed[j]，碰撞时间为 (position[j] - position[i]) / (speed[i] - speed[j])。

  2. 关键洞察：我们从右往左遍历，对于当前车辆，需要找到它能碰撞的第一辆车。但有些车辆可能永远不会成为碰撞目标，需要优化掉。

  3. 单调栈优化：

    • 如果右侧有两辆车 A 和 B（A 在 B 左边），且当前车能在碰撞 B 之前先碰撞 A，那么 A 会"屏蔽"B
    • 我们维护一个栈，确保栈中的车辆按照碰撞时间单调递增
    • 对于当前车辆，先移除速度不小于当前车的车辆（无法碰撞）
    • 然后移除会被"屏蔽"的车辆

  4. 具体步骤：

    • 从右往左遍历每辆车
    • 维护一个栈存储可能的碰撞目标
    • 对于每辆车，清理栈中不合适的车辆
    • 计算与栈顶车辆的碰撞时间

推荐解法：使用单调栈，时间复杂度 O(n)，是最优解法。

代码实现

class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        int n = cars.size();
        vector<double> result(n, -1.0);
        vector<int> stack;
        
        auto getCollisionTime = [&](int i, int j) -> double {
            return (double)(cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]);
        };
        
        for (int i = n - 1; i >= 0; i--) {
            // 移除速度大于等于当前车的车辆
            while (!stack.empty() && cars[stack.back()][1] >= cars[i][1]) {
                stack.pop_back();
            }
            
            // 移除会被屏蔽的车辆
            while (stack.size() > 1) {
                int j = stack.back();
                int k = stack[stack.size() - 2];
                if (getCollisionTime(i, j) <= getCollisionTime(j, k)) {
                    break;
                }
                stack.pop_back();
            }
            
            if (!stack.empty()) {
                result[i] = getCollisionTime(i, stack.back());
            }
            
            stack.push_back(i);
        }
        
        return result;
    }
};

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        n = len(cars)
        result = [-1.0] * n
        stack = []
        
        def get_collision_time(i, j):
            return (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])
        
        for i in range(n - 1, -1, -1):
            # 移除速度大于等于当前车的车辆
            while stack and cars[stack[-1]][1] >= cars[i][1]:
                stack.pop()
            
            # 移除会被屏蔽的车辆
            while len(stack) > 1:
                j, k = stack[-1], stack[-2]
                if get_collision_time(i, j) <= get_collision_time(j, k):
                    break
                stack.pop()
            
            if stack:
                result[i] = get_collision_time(i, stack[-1])
            
            stack.append(i)
        
        return result

public class Solution {
    public double[] GetCollisionTimes(int[][] cars) {
        int n = cars.Length;
        double[] result = new double[n];
        for (int i = 0; i < n; i++) {
            result[i] = -1.0;
        }
        
        Stack<int> stack = new Stack<int>();
        
        double GetCollisionTime(int i, int j) {
            return (double)(cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            // 移除速度大于等于当前车的车辆
            while (stack.Count > 0 && cars[stack.Peek()][1] >= cars[i][1]) {
                stack.Pop();
            }
            
            // 移除会被屏蔽的车辆
            while (stack.Count > 1) {
                int j = stack.Peek();
                stack.Pop();
                int k = stack.Peek();
                stack.Push(j);
                
                if (GetCollisionTime(i, j) <= GetCollisionTime(j, k)) {
                    break;
                }
                stack.Pop();
            }
            
            if (stack.Count > 0) {
                result[i] = GetCollisionTime(i, stack.Peek());
            }
            
            stack.Push(i);
        }
        
        return result;
    }
}

var getCollisionTimes = function(cars) {
    const n = cars.length;
    const result = new Array(n).fill(-1.0);
    const stack = [];
    
    const getCollisionTime = (i, j) => {
        return (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]);
    };
    
    for (let i = n - 1; i >= 0; i--) {
        // 移除速度大于等于当前车的车辆
        while (stack.length > 0 && cars[stack[stack.length - 1]][1] >= cars[i][1]) {
            stack.pop();
        }
        
        // 移除会被屏蔽的车辆
        while (stack.length > 1) {
            const j = stack[stack.length - 1];
            const k = stack[stack.length - 2];
            if (getCollisionTime(i, j) <= getCollisionTime(j, k)) {
                break;
            }
            stack.pop();
        }
        
        if (stack.length > 0) {
            result[i] = getCollisionTime(i, stack[stack.length - 1]);
        }
        
        stack.push(i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，每辆车最多被压入和弹出栈一次
空间复杂度O(n)，栈的最大大小为 n

相关题目