【单调栈】LeetCode1776:车队

作者推荐

【贪心算法】【中位贪心】.执行操作使频率分数最大

涉及知识点

单调栈

题目

在一条单车道上有 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 <= 10⁵
1 <= position_{i} , speed_{i} <= 10⁶
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 = 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<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<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++ 实现。