牛客 20806 Bad Hair Day
题目意思 牛1向右看,看得见 牛2,3,4, 看不见 牛5 以及 牛5之后的牛。 求每个牛能看见牛的个数。
1 2 3 4 5 6 O O OO O OOO O OOOOOO
题解:维护一个单调递减栈,只要求每个最大值的右区间即可)。
#include <cstdio> #include <iostream> #include <stack> typedef long long int ll; const int MAXN = 8e4 + 3; using namespace std; ll height[MAXN]; int main(){ int N; ll ans = 0; cin >> N; for(int i=0;i<N;i++) cin >> height[i]; height[N] = 1e10; stack<int> s; for(int i=0;i<=N;i++){ while(!s.empty()&&height[s.top()] <= height[i]){ ans += (i-s.top()-1); s.pop(); } s.push(i); } cout << ans << endl; return 0; }转载于:https://www.cnblogs.com/--zz/p/11242869.html
相关资源：JAVA上百实例源码以及开源项目