ACM-单调队列

对于单调队列的基本概念可以去看百科里的相关介绍：http://baike.baidu.com/view/3771451.htm

这里挑一些重点。

作用：

不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小的元素。

最直接的方法：普通队列实现缓存数组。

进队出队都是O(1)，一次查询需要遍历当前队列的所有元素，故O(n)。

RMQ即Range Maximum(Minimum) Query，用来求某个区间内的最大值或最小值。使用线段树或稀疏表是O(log(n))级的。对于这类问题这两种方法也搞得定，但是没有单调队列快。

定位：

大多数题目为单调队列力所不能及的，取而代之的是单调队列基础上改进的斜率优化，单调栈等，因为其限制条件，故潜力不大。但需要掌握，因为有许多算法建立在其基础上。

简单说就是基础，得会。

poj 2823

http://acm.hust.edu.cn/vjudge/problem/16694

k大小的滑动窗口，求每次窗口中最大值和最小值

思路：

维护单增队列和单减队列，因为滑动窗口和index有关，所以加个index数组维护head的索引

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!
")
#define MAXN 1000000+5
#define MAX(a,b) a>b?a:b
#define blank pf("
")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f

#define ls (rt<<1)
#define rs (rt<<1|1)

int n,m,k;

int a[MAXN],qu[MAXN],index[MAXN],ans[MAXN];

void getMin()
{
    int head=1,tail=0;
    for(int i =1;i<k;i++)
    {
        while(head<=tail && a[i]<=qu[tail]) tail--;
        qu[++tail] = a[i];
        index[tail] = i;
    }
    for(int i=k;i<=n;i++)
    {
        while(head<=tail && a[i]<=qu[tail]) tail--;
        qu[++tail] = a[i];
        index[tail] = i;
        while(index[head]<= i-k) head++;
        ans[i-k] = qu[head];
    }
}

void getMax()
{
    int head=1,tail=0;
    for(int i =1;i<k;i++)
    {
        while(head<=tail && a[i]>=qu[tail]) tail--;
        qu[++tail] = a[i];
        index[tail] = i;
    }
    for(int i =k;i<=n;i++)
    {
        while(head<=tail && a[i]>=qu[tail]) tail--;
        qu[++tail] = a[i];
        index[tail] = i;
        while(index[head]<= i-k) head++;
        ans[i-k] = qu[head];
    }
}

int main()
{
    int i,j,t,kase=1;
    while(~sf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) sf("%d",&a[i]);
        getMin();
        for(i=0;i<=n-k;i++) pf("%d ",ans[i]);
        blank;
        getMax();
        for(i=0;i<=n-k;i++) pf("%d ",ans[i]);
        blank;
    }
    return 0;
}