关于单调队列的解释，这里有篇博文我认为讲得很好：

，可以参考。我自己简单的总结了一下单调队列这种数据结构的性质：

    1 、在队列里的元素一定是value单调递增（或者递减），而index单调递增。所以         队列中的头元素要么最大，要么最小。

       怎么保证这种性质呢，很简单，留在队列的元素在数组中并不是连续的。比如         array=1 4 7 3 2 ,在某个时刻，队列头元素为4，那么队列的结构有可能是4         3 2，而7就被跳过了。

    2、 单调队列只允许从末尾加入元素，而允许从两端删除元素。

   我这里就只贴代码，我这里用了两种方式来实现单调队列。针对poj2823那道题。

   第一种：运用STL的Deque(双端队列)：

1. #include<deque> #include<stdio.h> using namespace std; #define M 1000005 int a[M]; char ch[2*M]; int n,k; int index; int getInt(){ int u=1,data=0; while(ch[index]<='0'||ch[index]>='9')index++; if(index>0&&ch[index-1]=='-')u=-1; while(ch[index]>='0'&&ch[index]<='9'){ data=data*10+ch[index]-'0'; index++; } return data*u; } int main(){ scanf("%d %d",&n,&k); int i; getchar(); gets(ch); index=0; for(i=1;i<=n;i++){ a[i]=getInt(); } deque<pair<int,int> > D(M); for(i=1;i<k;i++){ while(!D.empty()&&a[i]<=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); } for(i=k;i<=n;i++){ while(!D.empty()&&a[i]<=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); while(D.front().second<=i-k)D.pop_front(); printf("%d ",D.front().first); } printf("\n");D.clear(); for(i=1;i<k;i++){ while(!D.empty()&&a[i]>=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); } for(i=k;i<=n;i++){ while(!D.empty()&&a[i]>=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); while(D.front().second<=i-k)D.pop_front(); printf("%d ",D.front().first); } return 0; }
2.  

这一种在poj上提交超时。

第二种：自己用数组实现单调队列：

1. #include<stdio.h> 
2. #define M 2000005 
3. int a[M],Q[M],I[M]; 
4. int i,n,k; 
5. void getMax(){ 
6.     int head=1,tail=0; 
7.     for(i=1;i<k;i++){ 
8.         while(head<=tail&&Q[tail]<=a[i])tail--; 
9.         tail++; 
10.         Q[tail]=a[i];I[tail]=i; 
11.     } 
12.     for(i=k;i<=n;i++){ 
13.         while(head<=tail&&Q[tail]<=a[i])tail--; 
14.         tail++; 
15.         Q[tail]=a[i];I[tail]=i; 
16.         while(I[head]<=i-k)head++; 
17.         printf("%d ",Q[head]); 
18.     } 
19. } 
20. void getMin(){ 
21.     int head=1,tail=0; 
22.     for(i=1;i<k;i++){ 
23.         while(head<=tail&&Q[tail]>=a[i])tail--; 
24.         tail++; 
25.         Q[tail]=a[i];I[tail]=i; 
26.     } 
27.     for(i=k;i<=n;i++){ 
28.         while(head<=tail&&Q[tail]>=a[i])tail--; 
29.         tail++; 
30.         Q[tail]=a[i];I[tail]=i; 
31.         while(I[head]<=i-k) head++; 
32.         printf("%d ",Q[head]); 
33.     } 
34. } 
35. int main(){ 
36.     scanf("%d %d",&n,&k); 
37.     for(i=1;i<=n;i++) 
38.         scanf("%d",&a[i]); 
39.     getMin(); 
40.     printf("\n"); 
41.     getMax(); 
42.     return 0; 
43. } 

这种就AC了。注明一下，第二种是我在网上找到的代码，不是自己写的！