今天学习了一下单调队列这种数据结构，思想不是很难
参考资料：http://www.cnblogs.com/Jason-Damon/archive/2012/04/19/2457889.html
然后自己写成了类的模板形式，并做了例题poj2823
代码如下：
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define maxn 10000010
typedef struct Node
{
int val;
int num;
}node;
typedef struct iqueue
{
node q[maxn];
int l,r;
void ini()
{
l=;
r=;
}
node front()
{
return q[l];
}
node pop()
{
l++;
return q[l-];
}
void push(node x)
{
if(r==l)
{
q[r++]=x;
return;
}
if(x.val>=q[l].val)
{
r=l;
q[r++]=x;
return;
}
while(r>=&&x.val>=q[r-].val)
{
r--;
}
q[r++]=x;
}
}Iqueue;
typedef struct dqueue
{
node q[maxn];
int l,r;
void ini()
{
l=;
r=;
}
node front()
{
return q[l];
}
node pop()
{
l++;
return q[l-];
}
void push(node x)
{
if(r==l)
{
q[r++]=x;
return;
}
if(x.val<=q[l].val)
{
r=l;
q[r++]=x;
return;
}
while(r>=&&(x.val<=q[r-].val))
{
r--;
}
q[r++]=x;
}
}Dqueue;
int big[];
int small[];
Iqueue qi;
Dqueue qd;
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
node x;
node s,b;
int t=;
qi.ini();
qd.ini();
for(int i=;i<=n;i++)
{
scanf("%d",&x.val);
x.num=i;
qi.push(x);
qd.push(x);
if(i>=k)
{
b=qi.front();
while(b.num<=i-k)
{
qi.pop();
b=qi.front();
}
s=qd.front();
while(s.num<=i-k)
{
qd.pop();
s=qd.front();
}
big[t]=b.val;
small[t++]=s.val;
}
}
for(int i=;i<t;i++)
{
printf("%d",small[i]);
if(i==t-)
puts("");
else
printf(" ");
}
for(int i=;i<t;i++)
{
printf("%d",big[i]);
if(i==t-)
puts("");
else
printf(" ");
}
}
return ;
}