作者推荐
【贪心算法】【中位贪心】.执行操作使频率分数最大
本文涉及的基础知识点
单调栈分类、封装和总结
题目
在一条单车道上有 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<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 = ();
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[()] > 0 ) && (dMeetTime >= vRet[iPre]))
{
sta.pop();
}
else
{
break;
}
}
}
if (sta.size())
{
const int iPre = ();
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<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[()]
#define MeetTime ((double)PreCar[0] - CurCar[0])/(CurCar[1] - PreCar[1])
#define NeedMove1 (CurCar[1] <= PreCar[1])
#define NeedMove2 (vRet[()] > 1e-9) && ( MeetTime > vRet[()])
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<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 = ();
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;
};
