单调栈与单调队列简单例题

单调栈：

POJ3250

题意：有n只奶牛排成一列向右看，每头奶牛只能看到比自己矮的奶牛，即会被高的奶牛挡住后面，问共有多少只奶牛能被看到

思路：考虑每头奶牛能被前面牛看到的次数，也就是从他左边开始单调递减的序列的长度，用单调栈维护即可

代码：

#include<cstdio> #include<stack> using namespace std; const int maxn = 80005; stack<int > s; int main() { int n,x; long long sum = 0; scanf("%d",&n); scanf("%d",&x); s.push(x); for(int i = 1;i < n;i++) { scanf("%d",&x); while(!s.empty() && s.top() <= x) s.pop(); sum += s.size(); s.push(x); } printf("%lld\n",sum); return 0; }

单调队列：

Poj2823(这题好像要用c++交才能过)

题意：给出一个长度为n的序列和区间长度k,从左向右对每一个长度为k的区间询问最大值和最小值。

思路：对于最小值，考虑维护一个递增的双端队列，每次入队时将队尾比当前入队元素的全部删除，每次取队首并且判断是否在当前区间内即可

代码：

#include<cstdio> #include<deque> #include<iostream> #include<algorithm> #include<utility> using namespace std; const int maxn = 1e6+5; deque<int> Q1,Q2; int a[maxn]; int n,k; void solve1() { for(int i = 1;i <= n;i++) { while(!Q1.empty() && a[Q1.back()] >= a[i]) Q1.pop_back(); Q1.push_back(i); if(i>=k) { while(!Q1.empty() && Q1.front() < i-k+1) Q1.pop_front(); printf("%d ",a[Q1.front()]); } } } void solve2() { for(int i = 1;i <= n;i++) { while(!Q2.empty() && a[Q2.back()] <= a[i]) Q2.pop_back(); Q2.push_back(i); if(i>=k) { while(!Q2.empty() && Q2.front() < i-k+1) Q2.pop_front(); printf("%d ",a[Q2.front()]); } } } int main() { scanf("%d%d",&n,&k); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); solve1(); printf("\n"); solve2(); return 0; }

转载于:https://www.cnblogs.com/pot-a-to/p/11180802.html