信奥赛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。

解题思路

1. 维护单调递减栈（栈顶最小）
2. 逆序遍历数组（从右向左）
3. 如果当前元素 >= 栈顶元素时，持续弹出栈顶
4. 记录第一个大于当前元素的栈顶元素
5. 当前元素入栈

代码实现

#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;}

执行过程图解（样例数据）

更多系列知识，请查看专栏：《信奥赛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;}