找出数组中每个数的右边第一个比它大的数

给定一个乱序数组,找出每个数的右边第一个比它大的数。

例子:

输入[9, 6, 5, 7, 3, 2, 1, 5, 9, 10]

输出[10,7,7,9,5,5,5,9,10,N]

答案

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> findMax(vector<int>num)
{

	if (num.size() == 0)return num;
	vector<int>res(num.size());
	int i = 0;
	stack<int>s;
	while (i<num.size())
	{
		if (s.empty() || num[s.top()] >= num[i])
		{
			s.push(i++); // 只有在这种情况下才i++,因为num[i]还有可能是更前面的数字的第一个最大的数,理解这一点非常重要。
		}
		else
		{
			res[s.top()] = num[i];
			s.pop();
		}
	}
	while (!s.empty())
	{
		res[s.top()] = INT_MAX;
		s.pop();
	}
	for (int i = 0; i<res.size(); i++)
		cout << res[i] << endl;
	return res;
}
int main()
{
	vector<int>p{ 9, 6, 5, 7, 3, 2, 1, 5, 9, 10 };
	vector<int> res = findMax(p);
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

17 − 1 =

− 3 = 1