信奥赛C++提高组csp-s之单调栈（案例实践2）
信奥赛C++提高组csp-s之单调栈（案例实践2）
【模板】单调栈
题目描述
给出项数为n nn的整数数列a 1 … n a_{1 \dots n}a1…n。
定义函数f ( i ) f(i)f(i)代表数列中第i ii个元素之后第一个大于a i a_iai的元素的下标，即f ( i ) = min i < j ≤ n , a j > a i { j } f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}f(i)=mini<j≤n,aj>ai{j}。若不存在，则f ( i ) = 0 f(i)=0f(i)=0。
试求出f ( 1 … n ) f(1\dots n)f(1…n)。
输入格式
第一行一个正整数n nn。
第二行n nn个正整数a 1 … n a_{1\dots n}a1…n。
输出格式
一行n nn个整数表示f ( 1 ) , f ( 2 ) , … , f ( n ) f(1), f(2), \dots, f(n)f(1),f(2),…,f(n)的值。
输入输出样例 1
输入 1
5 1 4 2 3 5输出 1
2 5 4 5 0说明/提示
【数据规模与约定】
对于30 % 30\%30%的数据，n ≤ 100 n\leq 100n≤100；
对于60 % 60\%60%的数据，n ≤ 5 × 10 3 n\leq 5 \times 10^3n≤5×103；
对于100 % 100\%100%的数据，1 ≤ n ≤ 3 × 10 6 1 \le n\leq 3\times 10^61≤n≤3×106，1 ≤ a i ≤ 10 9 1\leq a_i\leq 10^91≤ai≤109。
解题思路
- 维护单调递减栈（栈顶最小）
- 逆序遍历数组（从右向左）
- 如果当前元素 >= 栈顶元素时，持续弹出栈顶
- 记录第一个大于当前元素的栈顶元素
- 当前元素入栈
代码实现
#include<iostream>usingnamespacestd;constintMAXN=3e6+5;inta[MAXN],res[MAXN],stk[MAXN],top=0;intmain(){intn;cin>>n;for(inti=1;i<=n;++i)cin>>a[i];for(inti=n;i>=1;--i){while(top&&a[stk[top]]<=a[i])top--;// 弹出不符合条件的元素res[i]=top?stk[top]:0;// 记录结果stk[++top]=i;// 当前索引入栈}for(inti=1;i<=n;++i)cout<<res[i]<<" ";return0;}执行过程图解（样例数据）
| 当前i | a[i] | 栈状态（底→顶） | 操作 | res[i] |
|---|---|---|---|---|
| 5 | 5 | 空 | 入栈 | 0 |
| 4 | 3 | [5] | 3<5 | 5 |
| 3 | 2 | [5,4] | 2<3 | 4 |
| 2 | 4 | [5,4,3] | 弹出3,4→4>2 | 5 |
| 1 | 1 | [5,2] | 1<4 | 2 |
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html
配套视频课信奥赛C++提高组csp-s知识详解：
https://edu.csdn.net/course/detail/41081
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}