P5788 【模板】单调栈

传送门

题目描述

给出项数为 \(n\) 的整数数列 \(a_{1 \dots n}\)。

定义函数 \(f(i)\) 代表数列中第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素的下标，即 \(f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}\)。若不存在，则 \(f(i)=0\)。

试求出 \(f(1\dots n)\)。

输入格式

第一行一个正整数 \(n\)。

第二行 \(n\) 个正整数 \(a_{1\dots n}\)。

输出格式

一行 \(n\) 个整数表示 \(f(1), f(2), \dots, f(n)\) 的值。

样例 #1

样例输入 #1

5
1 4 2 3 5

样例输出 #1

2 5 4 5 0

提示

【数据规模与约定】

对于 \(30\%\) 的数据，\(n\leq 100\)；

对于 \(60\%\) 的数据，\(n\leq 5 \times 10^3\) ；

对于 \(100\%\) 的数据，\(1 \le n\leq 3\times 10^6\)，\(1\leq a_i\leq 10^9\)。

前要芝士：单调栈

什么是单调栈：

单调栈：顾名思义，单调栈即满足单调性的栈结构。

简单来说，就是栈内的数一直保持递增或递减的关系。

实现：

插入: 每次插入时为保证栈内递增或递减，我们将栈顶的元素不断与将插入的数进行比较，如果不能符合数字插入后保持递增或递减，就将栈顶元素删除。这样可以有效保证栈内保持单调性，这就是单调队列的插入操作。

我们可以使用如下代码模拟插入(以单调递增为例)：

scanf("%d")
while(!q.empty()&&q.top()<x)
  q.pop();
q.push(x);

本题思路

我们使用单调递增的单调栈存储数组下标 (因为题目要求输出数组下标)，如果一个数被弹出，就说明找到了从自身往右数的第一个大于它的数，如果直到结束也没有弹出，就说明右边没有比它大的数字了(不理解的自行看代码和模拟)。

ACcode

#include<bits/stdc++.h>
using namespace std;
const int N=3*1e6+10;
int n,a[N],r[N];
stack<int> q;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&a[q.top()]<a[i])  //存储数字下标
		{
		   	r[q.top()]=i;               //存储答案
			 q.pop();
		}
		q.push(i);
	}
	for(int i=1;i<=n;i++)
		cout<<r[i]<<' ';
	return 0;
}

如果觉得不错的话点个关注喵~qwq