牛客BadHairDay题解（单调栈）
发布时间
阅读量：
阅读量
原题链接：https://ac.nowcoder.com/acm/problem/25084
解题思路：以队列末端为起点，建立一个单调递增的栈结构，在每头牛的身高被压入栈之前，需确保栈中所有牛的身高均高于当前牛，这样每头牛入栈时，栈中已有的所有元素所对应的牛均可看见当前牛，因此此时栈内元素的数量即为新增的可见数量，最终所有牛能够看到的总数应累加栈中元素的数量
①正向运用单调栈原理
②深入领会单调栈所蕴含的逻辑意义
#include<iostream>
#include<cstdio>
using namespace std;
int a[80010], n, top = 0;
int main()
{
scanf("%d",&n);
long long ans = 0;
while(n--){
int x;
scanf("%d",&x);
while(top && a[top-1] <= x){//如果此时栈不空，将个头比当前牛矮的牛出栈
top--;
}
ans += top;//总数加上此时栈内牛的个数
a[top++] = x;//将新来的牛入栈
}
printf("%ll全部评论 (0)
还没有任何评论哟~