【单调栈】LeetCode:1944队列中可以看到的人数

发布时间:2023年12月21日

作者推荐

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

题目

有 n 个人排成一个队列,从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ,每个整数 互不相同,heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的,第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], …, heights[j-1]) 。
请你返回一个长度为 n 的数组 answer ,其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。
示例 1:
输入:heights = [10,6,8,5,11,9]
输出:[3,1,2,1,1,0]
解释:
第 0 个人能看到编号为 1 ,2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。
示例 2:
输入:heights = [5,1,2,3,10]
输出:[4,1,1,1,0]
提示:
n == heights.length
1 <= n <= 105
1 <= heights[i] <= 105
heights 中所有数 互不相同

分析

从右向左遍历所有人(i从大到小),sta记录所有右边的人。如果i1 < i2,且heights[i1] > hights[i2],则前面的任何人到看不到i2,被i1所挡。淘汰i2后,sta从栈底到栈顶降序。
如果当前元素高于栈顶元素,则当前元素看得到栈顶。两者之间没有人高于等于栈顶之人,否则栈顶之人早出栈了。
注意:栈顶第一个高于等于当前人也可以看到,只是看不到后面的人。
时间复杂度: o(n),每个人顶多出栈入栈一次。

代码

核心代码

class Solution {
public:
	vector<int> canSeePersonsCount(vector<int>& heights) {
		m_c = heights.size();
		vector<int> vRet(m_c);
		stack<int> sta;
		for (int i = m_c - 1; i >= 0; i--)
		{
			while (sta.size() && (sta.top() < heights[i]))
			{
				vRet[i]++;
				sta.pop();
			}
			vRet[i] += !sta.empty();
			while (sta.size() && (sta.top()== heights[i]))
			{
				sta.pop();
			}
			sta.emplace(heights[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<int> heights;
	{
		Solution slu;
		heights = { 10,6,8,5,11,9 };
		auto res = slu.canSeePersonsCount(heights);
		Assert({ 3,1,2,1,1,0 }, res);
	}
	{
		Solution slu;
		heights = { 5,1,2,3,10 };
		auto res = slu.canSeePersonsCount(heights);
		Assert({ 4,1,1,1,0 }, res);
	}
	
	
	//CConsole::Out(res);
}

2023年3月版:二分查找

class Solution {
public:
vector canSeePersonsCount(vector& heights) {
m_c = heights.size();
vector vRet(m_c);
vector vDescHeight;
for (int i = m_c - 1; i >= 0; i–)
{
auto iNum = std::upper_bound(vDescHeight.begin(), vDescHeight.end(), heights[i],std::greater()) - vDescHeight.begin();
if (iNum > 0)
{
vRet[i] = vDescHeight.size() - (iNum - 1);
}
else
{
vRet[i] = vDescHeight.size();
}
while (vDescHeight.size() && (vDescHeight.back() <= heights[i]))
{
vDescHeight.pop_back();
}
vDescHeight.push_back(heights[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++ 实现。

文章来源:https://blog.csdn.net/he_zhidan/article/details/135098860
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。