题目描述

在一条单车道上有 n 辆车，它们朝着同样的方向行驶。给你一个长度为 n 的数组 cars，其中 cars[i] = [position_i, speed_i]，它表示：

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

简单起见，所有车子可以视为在数轴上移动的点。当两辆车占据同一个位置时，我们称它们相遇了。一旦两辆车相遇，它们会合并成一个车队，这个车队里的车有着同样的位置和相同的速度，速度为这个车队里 最慢 一辆车的速度。

请你返回一个数组 answer，其中 answer[i] 是第 i 辆车与下一辆车相遇的时间（单位：秒），如果这辆车不会与下一辆车相遇，则 answer[i] 为 -1。答案精度误差需在 10^-5 以内。

样例

输入：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 的车队。

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

限制

• 1 <= cars.length <= 10^5
• 1 <= position_i, speed_i <= 10^6
• position_i < position_i+1

算法

(单调栈) $O(n)$

1. 因为前边的车不会影响到当前车的合并情况，所以我们从第 $n$ 辆车开始考虑。显然第 $n$ 辆车的答案为 $-1$。
2. 对于第 $i$ 辆车，找到第 $j$ 辆车，满足 $s_j < s_i$ 且 $\frac{p_j - p_i}{s_i - s_j}$ 最小，答案为最小值。如果不存在这样 $j$，则答案为 $-1$。
3. 但暴力的时间复杂度为 $O(n^2)$，需要优化。
4. 进一步注意到
   • 每一辆车都依赖紧跟的后一辆车所代表的车队来计算时间，关键在于如何确定后一辆车所组成的车队。
   • 如果 $s_j \ge s_i$，则 $i$ 无论如何都不会在 $j$ 遇到其他车并且减速之前，和 $j$ 相遇，此时 $j$ 完全可以被 $i$ 取代。
   • 如果同时存在比 $j_0$ 的车队更靠后的 $j_1$ 的车队，但 $j_1$ 计算出的时间小于等于 $j_0$ 计算的时间，此时 $j_0$ 的车队必定会先遇到 $j_1$ 所代表的的车队，然后 $i$ 再同时遇到 $j_0$ 和 $j_1$ 的车队。此时，对于 $i$ 来说，$j_0$ 完全可以被 $j_1$ 取代。
5. 此时，可以利用单调栈的性质，每次求 $i$ 的值时，先通过不断和栈顶元素比较，废弃掉一些没用的 $j$，然后根据栈顶的值计算出答案（如果栈为空，则答案为 $-1$）。最后 $i$ 再进栈。

时间复杂度

• 每辆车最多进栈一次，出栈一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储单调栈和答案。

C++ 代码

#define LL long long

class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        const int n = cars.size();
        vector<double> ans(n);
        stack<int> st;
        ans[n - 1] = -1;
        st.push(n - 1);

        for (int i = n - 2; i >= 0; i--) {
            while (!st.empty()) {
                int top = st.top();
                st.pop();

                if (cars[i][1] <= cars[top][1])
                    continue;

                if (st.empty()) {
                    st.push(top);
                    break;
                }

                int t = st.top();
                if ((LL)(cars[top][0] - cars[i][0]) * (cars[i][1] - cars[t][1]) >=
                    (LL)(cars[t][0] - cars[i][0]) * (cars[i][1] - cars[top][1]))
                    continue;

                st.push(top);
                break;
            }

            if (st.empty())
                ans[i] = -1;
            else
                ans[i] = 1.0 * (cars[st.top()][0] - cars[i][0]) /
                               (cars[i][1] - cars[st.top()][1]);

            st.push(i);
        }
        return ans;
    }
};