【单调栈】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 <= 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 = 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++ 实现。

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
心中带点小风骚的头像心中带点小风骚普通用户
上一篇 2023年12月26日
下一篇 2023年12月26日

相关推荐

此站出售,如需请站内私信或者邮箱!