滑动最小值（双端队列）

给定一个长度为n的数列a(0),a(1),...,a(n-1)和一个整数k。求数列b(i)=min{a(i),a(i+1),...,a(i+k-1)}（i=0,1,2,3,...,n-k）;

限制条件：1<=k<=n<=10^6 0<=ai<=10^9

思路：类似用一个长度为k的窗在整数数列上滑动，求窗里面所包含的数的最小值；

可以使用RMQ在o（nlogn）复杂度内解决，本次介绍双端队列；

          双端队列（即单调队列），可以在头部和尾部插入和删除元素的数据结构；
          构造单调递增队列，初始双端队列为空，在加入i时，当队列的末尾的值j满足a[j]>=a[i]，则不断取出（构造一个递增队列），直到队列为空或者a[j]<a[i]之后再在末尾加入i。则双端队列头部即为最小值。

时间复杂度：由于双端队列的加入和删除都进行了o（n）次，故整个算法的复杂度为o（n）；

代码：

//输入
int n,k;
int a[maxn];

int 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]]>=a[i])   t--;//加入i时，判断双端队列末尾的值是否满足>=a[i]
         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?
: );
}