题目

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

思路

单调栈

解法

class Solution {
    public double[] getCollisionTimes(int[][] cars) {
        Deque<Integer> stack = new ArrayDeque<>();
        double[] ans = new double[cars.length];
        // 每辆车最终追上下一辆车的时间与前边的车没关系，所以倒着计算
        for (int i = cars.length - 1; i >= 0; i--) {
            while (!stack.isEmpty()) {
                int peek = stack.peek();
                /** 如果i车速度大于栈顶车的车速，这时计算自然状态下i车追上peek所需时间t，
                 * 如果t <= ans[peek] || ans[peek] == -1，说明i最终会经过时间t追上peek，
                 * 否则在i追上peek之前，peek已经追上它后面的车了，这时可以直接不考虑peek了，
                 * peek出栈，继续考虑i追击peek后面车的情况
                 */
                if (cars[i][1] > cars[peek][1]) {
                    double t = (cars[peek][0] - cars[i][0]) * 1.0 / (cars[i][1] - cars[peek][1]);
                    if (t <= ans[peek] || ans[peek] == -1) {
                        // i在时间t时追上peek
                        ans[i] = t;
                        break;
                    }
                }
                // i车最终不会追上peek 
                stack.pop();
            }
            // 如果栈为空，说明i追不上任何车
            if (stack.isEmpty()) ans[i] = -1;
            stack.push(i);
        }
        return ans;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现