信奥赛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_{ij\leq n, a_j a_i} \{j\}f(i)minij≤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输入 15 1 4 2 3 5输出 12 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×1061 ≤ a i ≤ 10 9 1\leq a_i\leq 10^91≤ai​≤109。解题思路维护单调递减栈栈顶最小逆序遍历数组从右向左如果当前元素 栈顶元素时持续弹出栈顶记录第一个大于当前元素的栈顶元素当前元素入栈代码实现#includeiostreamusingnamespacestd;constintMAXN3e65;inta[MAXN],res[MAXN],stk[MAXN],top0;intmain(){intn;cinn;for(inti1;in;i)cina[i];for(intin;i1;--i){while(topa[stk[top]]a[i])top--;// 弹出不符合条件的元素res[i]top?stk[top]:0;// 记录结果stk[top]i;// 当前索引入栈}for(inti1;in;i)coutres[i] ;return0;}执行过程图解样例数据当前ia[i]栈状态底→顶操作res[i]55空入栈043[5]35532[5,4]23424[5,4,3]弹出3,4→42511[5,2]142更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html配套视频课信奥赛C提高组csp-s知识详解https://edu.csdn.net/course/detail/41081各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}