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
1.本站内容仅供参考,不作为任何法律依据。用户在使用本站内容时,应自行判断其真实性、准确性和完整性,并承担相应风险。
2.本站部分内容来源于互联网,仅用于交流学习研究知识,若侵犯了您的合法权益,请及时邮件或站内私信与本站联系,我们将尽快予以处理。
3.本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
4.根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。
5.本站是非经营性个人站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途
暂无评论内容