下面文章抄袭到 hello kity的。。原文章地址请戳这里
/*******************************hello kity********************************************/
一直弄不明白单调队列是什么，在网上也找不到易懂的介绍。最后结合别人博客上的介绍和程序看才理解是怎么回事。
我们从最简单的问题开始：
给定一个长度为N的整数数列a(i),i=0,1,...,N-1和窗长度k.
要求：
f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1
问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。
解法一：
很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。
这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。
那么有没有更快一点的算法呢？
解法二：
我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。
单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。
1.首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。
2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于 i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首 元素删除。
从上面的介绍当中，我们知道，单调队列与队列唯一的不同就在于它不仅要保存元素的值，而且要保存元素的索引（当然在实际应用中我们可以只需要保存索引，而通过索引间接找到当前索引的值）。
为了让读者更明白一点，我举个简单的例子。
假设数列为：8，7，12，5，16，9，17，2，4，6.N=10,k=3.
那么我们构造一个长度为3的单调递减队列：
首先，那8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下：
0：插入8，队列为：（8，0）
1：插入7，队列为：（8，0），（7，1）
2：插入12，队列为：（12，2）
3：插入5，队列为：（12，2），（5，3）
4：插入16，队列为：（16，4）
5：插入9，队列为：（16，4），（9，5）
。。。。依此类推
那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，。。。
/***********************************************************************************/
先来一道简单单调队列题
题意：有N只奶牛，求每只奶牛能看到最远处奶牛的只数之和。。。
分析：纯单调递减队列
View Code #include <iostream> #include <cstdio> #include <cstring> #define MAXN 80050 #define LL long long using namespace std; LL q[MAXN]; int main() { int n; scanf("%d",&n); LL a; LL ans=0; int rear=-1,front=0; for(int i=0;i<n;i++){ scanf("%I64d",&a); while(rear>=front&&q[rear]<=a)rear--; q[++rear]=a; ans+=rear; } cout<<ans<<endl; return 0; }
一道经典的单调队列 POJ-2823-Sliding Window
这题要用c++交，g++交会超时。。。。
#include <iostream> #include <cstdio> #include <cstring> #define MAXN 1000050 using namespace std; int q[MAXN]; int a[MAXN]; int f[MAXN]; int n,m; void getMax(){ int head=0,rear=-1; for(int i=0;i<m-1;i++){ while(rear>=head&&q[rear]<a[i])rear--; q[++rear]=a[i]; f[rear]=i; } for(int i=m-1;i<n;i++){ while(rear>=head&&q[rear]<a[i])rear--; q[++rear]=a[i]; f[rear]=i; while(f[head]<=i-m)head++; if(i==n-1){ printf("%d",q[head]); continue; } printf("%d ",q[head]); } } void getMin(){ int head=0,rear=-1; for(int i=0;i<m-1;i++){ while(rear>=head&&q[rear]>a[i])rear--; q[++rear]=a[i]; f[rear]=i; } for(int i=m-1;i<n;i++){ while(rear>=head&&q[rear]>a[i])rear--; q[++rear]=a[i]; f[rear]=i; while(f[head]<=i-m)head++; if(i==n-1){ printf("%d",q[head]); continue; } printf("%d ",q[head]); } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } getMin(); printf("\n"); getMax(); printf("\n"); return 0; }