算法竞赛备考冲刺必刷题（C++） | 洛谷 P5788 单调栈

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P5788 【模板】单调栈 - 洛谷

【题目描述】

给出项数为n nn的整数数列a 1... n a_{1...n}a1...n​。

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

试求出f ( 1 … n ) f(1…n)f(1…n)。

【输入】

第一行一个正整数n nn。

第二行 nn 个正整数a 1 … n a_{1…n}a1…n​。

【输出】

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

【输入样例】

5 1 4 2 3 5

【输出样例】

2 5 4 5 0

【算法标签】

《洛谷 P5788 单调栈》 #线性数据结构# #栈# #单调栈# #模板题#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=3000005;// 数组大小常量intn,a[N],ans[N],q[N];// a: 输入数组, ans: 结果数组, q: 单调栈intmain(){scanf("%d",&n);// 读入数组长度// 读入数组元素for(inti=1;i<=n;i++)scanf("%d",&a[i]);inttop=0;// 栈顶指针，栈空时top=0// 从前往后遍历数组for(inti=1;i<=n;i++){// 当栈非空且当前元素大于栈顶元素时while(top>0&&a[q[top]]<a[i]){ans[q[top]]=i;// 记录栈顶元素的答案：第一个比它大的元素位置top--;// 弹出栈顶}q[++top]=i;// 将当前位置入栈}// 输出结果for(inti=1;i<=n;i++)printf("%d ",ans[i]);return0;}

// 使用acwing模板二刷#include<bits/stdc++.h>usingnamespacestd;constintN=3000006;// 定义数组大小，略大于3×10^6intn,a[N],ans[N],stk[N],tt;// a: 输入数组, ans: 结果数组, stk: 单调栈, tt: 栈顶指针intmain(){cin>>n;// 读入数组长度// 读入数组元素for(inti=1;i<=n;i++)cin>>a[i];// 单调栈算法for(inti=1;i<=n;i++){// 当栈不为空且当前元素大于栈顶元素时while(tt&&a[stk[tt]]<a[i]){ans[stk[tt]]=i;// 记录栈顶元素的下一个更大元素位置tt--;// 弹出栈顶}stk[++tt]=i;// 将当前索引入栈}// 输出结果for(inti=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;return0;}

【运行结果】

5 1 4 2 3 5 2 5 4 5 0