滑动最小值 /// 单调队列

题目大意：

输入n，k；给定长度为n的数列a0，a1，...，a(n-1)

求数列b=min(ai,ai+1,...,ai+k-1) i=0,1,...,n-k;

#include <bits/stdc++.h>
using namespace std;
int n,a[105],k,b[105];
int deq[105]; // 模拟双端队列 保存对应a[]下标
int main()
{
    while(~scanf("%d%d",&n,&k)) {
        for(int i=0;i<n;i++) scanf("%d",&a[i]);

        int head=0, tail=0; // 赋零清空队列
        for(int i=0;i<n;i++) {
            while(head<tail && a[deq[tail-1]]>=a[i]) tail--;
            /// 若deq[]对应的值>=a[i] 则一直推到比a[i]小或没有值
            deq[tail++]=i; // 更新队列

            if(i-k+1>=0) { // 若已满足k个
                b[i-k+1]=a[deq[head]]; // 将前k个内最小值存入b[]
                if(deq[head]==i-k+1) head++;
                /// 若队头的最小值已经是当前k个内的第一个
                /// 即继续往后时 deq[head]已经超出k个的限制
                /// 则舍弃这个最小值 head后移向下一个最小值
            }
        }

        for(int i=0;i<=n-k;i++)
            printf("%d%c",b[i], i==n-k ? '
':' ');
    }

    return 0;
}
/*
n=5,k=3
a={1,3,5,4,2}

i  a[]  deq[]               b[]
  1   0(1)
  3   0(1) 1(3)
  5   0(1) 1(3) 2(5)      1
  4   1(3) 2(5) 3(4)
        1(3) 3(4) /// 因为5>4 tail--;
        3(4) /// 1(3)已经不在k个的范围内 删掉 head++;
4   2   3(4) 4(2)
        4(2) /// 因为4>2 tail--;
最后 b={1,4,2}
*/