LeetCode 1776. 车队 II（单调栈）

示例 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^5
1 <= positioni, speedi <= 10^6
positioni < positioni+1

class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        int n = cars.size();
        vector<double> ans(n, -1.0);
        stack<int> s;
        for(int i = n-1; i >= 0; i--) 
        {
            while(!s.empty() && (cars[s.top()][1] >= cars[i][1] || (ans[s.top()] > 0 && delta(cars, i, s.top()) > ans[s.top()])))
            {   // 我的速度没有前车大，追不上前面的，检查再前面的人，前面可能有更慢的
                //前车 top 能撞上别人 且 撞上别人的时间 小于 我撞上top的时间，那我应该去跟更前面的人计算
                // 因为前车 top 已经先于我 撞上更前面的
                s.pop();
            }
            if(!s.empty())
                ans[i] = delta(cars, i, s.top());
            s.push(i);
        }
        return ans;
    }
    double delta(vector<vector<int>>& cars, int i, int j)//j 位置远，速度慢
    {
        return (cars[j][0] - cars[i][0])/double(cars[i][1] - cars[j][1]);
    }
};