题目
在一条单车道上有 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 <= position_{i} , speed_{i} <= 106
positioni < positioni+1
单调栈
车队的前后和数组的前后相反，按车队从前到后枚举i（i从大到小)。
有如下规律：
一，车队的第一辆车不会降速。所以相遇的时候只考虑车队头。
二，前面的车比当前车块，则不会被当前车追上。
三，一辆车在被追上前，追上前面的车。则不会成为车队头。
四，后面的车不能越过当前车，可以将二三的"当前车"扩大为"当前车及后面的车"。即情况二三的车被淘汰。
五，除栈顶的车外，都有可能成为车头，否则早被淘汰了。
规则二，使得前面速度快的车被淘汰，于是栈中的速度升序，形成单调栈。
代码
核心代码
class Solution { public: vector<double> getCollisionTimes(vector<vector<int>>& cars) { m_c = cars.size(); vector<double> vRet(m_c, -1); stack<int> staIndex; for (int i = m_c - 1; i >= 0; i--) { while (staIndex.size() && (cars[staIndex.top()][1] >= cars[i][1])) {//淘汰速度快的车，当前车追不上。后面的车也追不上 staIndex.pop(); } #define MeetTime (((double)cars[staIndex.top()][0] - cars[i][0]) / (cars[i][1] - cars[staIndex.top()][1])) auto MeetPre = [&]() { if (staIndex.empty() || (vRet[staIndex.top()] < 0)) { return false; } return MeetTime >= vRet[staIndex.top()]; }; while (MeetPre()) {//淘汰被追上前，就追上前面的车 staIndex.pop(); } if (staIndex.size()) { vRet[i] = MeetTime; } staIndex.emplace(i); } return vRet; } int m_c; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector<int>> cars; { Solution slu; cars = { {1,2},{2,1},{4,3},{7,2} }; auto res = slu.getCollisionTimes(cars); Assert({ 1.00000,-1.00000,3.00000,-1.00000 }, res); } { Solution slu; cars = { {3,4},{5,4},{6,3},{9,1} }; auto res = slu.getCollisionTimes(cars); Assert({ 2.00000,1.00000,1.50000,-1.00000 }, res); } //CConsole::Out(res); }
2023年3月版
class Solution { public: vector getCollisionTimes(vector& cars) { m_c = cars.size(); vector vRet(m_c, -1); std::stack sta;//碰撞时，可能的出头 sta.push(m_c - 1); for (int i = m_c - 1 - 1; i >= 0; i–) { while (sta.size()) { const int iPre = sta.top(); if (cars[i][1] <= cars[iPre][1]) {//速度慢或相等，永远无法撞上 sta.pop(); } else { const double dMeetTime = (double)(cars[iPre][0] - cars[i][0]) / (cars[i][1] - cars[iPre][1]); if ((vRet[sta.top()] > 0 ) && (dMeetTime >= vRet[iPre])) { sta.pop(); } else { break; } } } if (sta.size()) { const int iPre = sta.top(); const double dMeetTime = (double)(cars[iPre][0] - cars[i][0]) / (cars[i][1] - cars[iPre][1]); vRet[i] = dMeetTime; } else { vRet[i] = -1; } sta.push(i); } return vRet; } int m_c; };
2023年7月版
class Solution { public: vector getCollisionTimes(vector& cars) { m_c = cars.size(); std::stack sta; sta.emplace(m_c - 1); vector vRet(m_c, -1); for (int i = m_c - 2; i >= 0; i–) { //确保栈顶元素是相撞的车，两个条件：一，此车不能快于当前车 二，此车不能被撞之前撞上其它车 #define CurCar cars[i] #define PreCar cars[sta.top()] #define MeetTime ((double)PreCar[0] - CurCar[0])/(CurCar[1] - PreCar[1]) #define NeedMove1 (CurCar[1] <= PreCar[1]) #define NeedMove2 (vRet[sta.top()] > 1e-9) && ( MeetTime > vRet[sta.top()]) while (sta.size() && (NeedMove1 || NeedMove2)) { sta.pop(); } vRet[i] = sta.size() ? MeetTime : -1; sta.push(i); } return vRet; } int m_c; };
2023年9月版
class Solution { public: vector getCollisionTimes(vector& cars) { m_c = cars.size(); vector vRet(m_c,-1); std::stack sta; for (int i = m_c - 1; i >= 0; i–) { while (sta.size()) { int pre = sta.top(); if (cars[i][1] - cars[pre][1] <= 0) { sta.pop(); } else { double dMeet = (cars[pre][0] - cars[i][0]) / (double)(cars[i][1] - cars[pre][1]); if ((abs(vRet[pre] + 1) < 0.0001) || (dMeet < vRet[pre])) { vRet[i] = dMeet; break; } else { sta.pop(); } } } sta.emplace(i); } return vRet; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+
+17**
如无特殊说明，本算法用C++ 实现。
