双端队列（deque）的应用

问题描述：（滑动最小值）

 给定的一个长度为n的数列a0,a1,a2..an-1,和一个整数k，求数列bi=min(ai,ai+1..ai+k-1){i=0,1,..n-k}
 {1<=k<=n<=1e6;0<=ai<=1e9}
 sample input
 n=5
 k=3
 a={1,3,5,4,2}
 sample ouput
 b={1,3,2}
【分析】:
    solution 1:
        RMQ :复杂度O(nlogn)
    solution 2:
        deque <双端队列:可以在头部和尾部插入和删除元素的数据结构> 在O(n)时间内解决
【思路】:
    最开始时双端队列为空，然后不断维护双端队列使它按照如下顺序，注意保存的是后面的最小值的a数组的元素下标

    设双端队列从头部开始的元素为值为xi,则xi<xi+1 && a(xi)<a(xi+1)
    首先，为了计算b0,把0到 k-1 依次加入队列，在加入i时，当双端队列的末尾的值j满足aj>=ai,则不断取出
    直到双端队列为空或者aj<ai之后再在末尾加入i
    
    等到 k-1 都加入到队列里面，查看队列头部的值j，那么b0=aj,如果j==0,那么在之后的计算不会用到，所以删去
    接下来，为了计算bi,需要在队列的末尾加入k, 不断加入元素，就可以计算后面的bi的值，由于双端队列的加入和       删除都进行了O(n)次，因此算法复杂度O(n)
    对于样例，队列模拟如下：
    add 0 -> {0} (存的是下标)
    add 1 -> {0,1}
    add 2 -> {0,1,2}
    b0=a0 =1;
    remove 0 -> {1,2}
    add 3 -> {1,3} (a2>=a3,因此删除2)
    b1=a1=3;
    remove 1 -> {3}
    add 4 -> {4}  (a3>=a4,因此删除3)
    b2=a4=2
代码实现:
 

//输入
int n,k;
int a[maxn],b[maxn];
int deq[maxn];//双端队列
void solve()
{
    int s=0,t=0; //双端队列的头部和末尾
    for(int i=0; i<n; ++i)
    {
        //在双端队列的末尾加入i
        while(s<t&&a[deq[t-1]]>=a[i]) t--;
        deq[t++]=i; 
        if(i-k+1>=0)
        {
            b[i-k+1]=a[deq[s]];
            if(deq[s]==i-k+1) s++;//从双端队列的头部删除元素
        }
    }
    for(int i=0; i<=n-k; ++i)
    {
        printf("%d%c",b[i],i==n-k?'\n':' ');
    }
}