1776-车队 II

在一条单车道上有 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

class Solution {
public:
    //这道题必须想清楚一点，那就是如果ans[i]有正值，那么一定是cars[i]和某个cars[j]（j>i且speed[j]<speed[i]）发生碰撞
    //相撞之后，所谓的融合，其实可以理解为cars[i]消失了，cars[j]状态不变
    //所以我们只关注一辆车右边，不关注其左边，它的左边对它没有任何影响。可以考虑从右往左遍历
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        vector<double>ans(cars.size());
        //设立一个单调栈，栈底最慢，栈顶最快
        stack<int>S;
        for(int i=cars.size()-1;i>=0;i--){
            while(S.size()){
                //如果栈顶比我快，我追不上它，可以考虑等它消失之后我去撞它前面的，所以将它pop
                if(cars[S.top()][1]>=cars[i][1])S.pop();
                //如果栈顶比我慢，我就决定去碰它了
                else{
                    //如果它不会消失，那我肯定能碰它，break
                    if(ans[S.top()]<0)break;
                    //如果它会消失，我需要计算一下在它消失之前能否追上它
                    double d=ans[S.top()]*(cars[i][1]-cars[S.top()][1]);
                    //能追上，那我肯定碰它，break
                    if(d>cars[S.top()][0]-cars[i][0])break;
                    //追不上，那算了，追它前面的车
                    else S.pop();
                }
            }
            if(S.empty())ans[i]=-1;
            else{
                //相对距离除以相对速度
                double t=double(cars[S.top()][0]-cars[i][0])/double(cars[i][1]-cars[S.top()][1]);
                ans[i]=t;
            }
            S.push(i);
        }
        return ans;
    }
};