【c++】CTGU2022春校赛原题详解
紧接上文：今天给大家看看另一个我觉得我可以做出来但是没做出来的题。
这题乍一看是不是很简单，别着急，时间复杂度限制为o(n)，也就是说朴素方法不能过题~
所以要使用单调栈(就是很单调的栈[doge])，这里的“单调”跟单调函数的单调是一个意思。
所以单调栈是从栈顶到栈底严格递增或递减的栈。
关于栈的基本使用，我就不赘述了，注释很多，大家请看吧
#include<iostream>
#include<stack>
using namespace std;
int main()
{
stack<int>s;
int n = 0;
scanf("%d", &n);
long long ans = 0;
int h = 0;
for (int i = 0; i < n; i++)
{ //这样遍历可能会被误解为是“向左看”，其实不是。假设我们第一个数10，入栈，后面的3比10小，ans就变成了1，则计算的不是3号往后看的人数，而是10号。
scanf("%d", &h);
while (!s.empty() && s.top() <= h) //刚开始是空的，所以第一个元素可以入栈
//这样遍历可能会被误解为是“向左看”，其实不是。假设我们第一个数10，入栈，后面的3比10小，ans就变成了1，则计算的不是3号往后看的人数，而是10号。
s.pop(); //如果栈顶的元素比输入的小，就把它剔除掉，直到找到小于现在的为止
ans += s.size();
s.push(h); //因为自己看不到自己，所以新人入栈要在计算的后面
}
printf("%lld", ans);
return 0;
}
希望和诸君共勉。
相关知识
【c++】CTGU2022春校赛原题详解
C++第二天
大英赛B类备赛经验分享
天津工艺美术职业学院 2022年创新创业校赛获奖情况 公示
NEC全国赛全球赛获奖者参赛经验分享
2023XuperCore开源区块链创新赛
转发 | 与三创赛的再次见面，你准备好了吗
在C++中有以下4条语句： static int hot=200; int &a
动物行为学奥赛历年真题试卷试卷习题及其答案
第六届中国国际“互联网+”大学生创新创业大赛湖北美术学院校赛获奖名单公示
网址: 【c++】CTGU2022春校赛原题详解 https://m.mcbbbk.com/newsview355143.html
| 上一篇: 昨天梦见白色刺猬 |
下一篇: 《英语专业师范类专业认证知识50 |
