题168.洛谷P2866 单调栈-Bad Hair Day S

题168.洛谷P2866 单调栈-Bad Hair Day S

一、题目

二、题解

题目要你计算牛往右看，每头牛能看到牛顶的数目之和。依题意我们想，往又右看，也就是只要右边的牛都比当前牛严格矮，那么就能看到牛顶，如果碰到一个不满足这个条件的牛直接让当前牛话下一个，不用再试了，显然这样的做法需要两个循环，效率不够高，怎么办？有没有办法可以只用一个循环来解决问题？
这样，我们不妨换个角度去想，不去想当前牛能够看到右边多少只牛的牛顶，我们去想当前牛能够被左边的多少只牛看到，可是一直再往右边遍历之前的牛都过掉了怎么办？哎，我们可以用栈来存一下之前的牛。再顺着往下想，存在栈里的牛要想看到当前遍历到的牛要满足什么条件？显然必须自栈底向上牛的高度严格递减(越往左的牛必须越高，不然就会有牛被稍微右边的牛挡住，这样就看不到当前牛了)，这就是单调栈。
以上述，我们每次遍历到一个牛我去把这个牛的高度和栈顶(栈已维持自底向上严格递减)的牛的高度比较，如果它比栈顶大或者相等，就把栈顶的牛pop掉，直到比它比栈顶小为止，去将此时栈中牛数(这些牛都是可以看到当前牛的)加到总数中，最终总数即为结果

#include <bits/stdc++.h>using namespace std;stack<int> s;int main()
{int N;cin>>N;long long res=0;for(int i=0;i<N;i++){int h;scanf("%d",&h);while(!s.empty()&&h>=s.top())//栈里头只存有机会看到位于他们右边高度为h的牛的牛顶的牛，也就是说，我的栈序列必须自底向上严格递减{s.pop();//淘汰没法看见当前高度h的牛的牛顶的牛}res+=s.size();//将能看见当前h的牛的牛顶的牛加到总数中s.push(h);//将当前高度h的牛入栈}cout<<res<<endl;
}