Bad Hair Day【单调栈】
----------------------------From nowcoder:https://ac.nowcoder.com/acm/contest/984/A-----------------------------------
n（1~80000），一开始写了个O(n^2)+剪的写法，果不其然地T了。折腾了一下实在想不出决定翻一下过的代码，发现是用deque做的，这才第一次接触到单调栈的题。
大致解法是：求最多看到m头牛，于是转换为求有m头牛可以被其后的牛看见。每次处理要保证栈中的牛能看见每次读入进来的牛，若新牛比原牛高则pop掉，直到遇到栈中比新牛高的牛。每次读入的牛处理后可被s.size()的牛看见。
以样例来说，一开始读一个高度为10的牛，此时栈中没有牛可以看见它，ans+=0。10入栈。
读3，可被栈中10看见，ans+=1，3入栈。
读7，可被10看见，不可被3看见，3pop掉，ans+=1，7入栈。
读4，可被10、7看见，ans+=2，4入栈。
读12，全不可见，清空栈，ans+=0，12入栈。
读2，可被12看见，ans+=1，2入栈。最后ans=5。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
deque <int> q;
int n;
scanf("%d",&n);
LL ans=0;
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
while(!q.empty()&&q.back()<=x) q.pop_back();
//printf("size:%d\n",q.size());
ans+=q.size();
q.push_back(x);
}
printf("%lld\n",ans);
}
查看14道真题和解析
投递欣旺达等公司6个岗位