（转自yyr洛谷博客）洛谷P2251 【质量检测】

转自yyr博客（https://www.luogu.org/blog/yeyangrui/）
（主要是想收录他的）
这一道题的主要思路：单调队列（不熟的可以做一下滑动窗口这一道题）**（表示蒟蒻不会ST表）

建立一个从小到大的单调队列，每次如果读入到比队尾的数小就将队尾的数弹出（贪心思想：你后面都有更小值的了你还要前面的干什么呢？反而长度更长更容易失效），另外不要忘了将已经超出整个序列长度的物体从队首弹出，的而每一组的答案就是这个单调队列的队首元素**

代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
int a[1000001];
struct node
{
    int a;//物体的质量
    int b;//物体的位置
}b[1000001];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,m,head=1,top=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i]; 
    for(int i=1;i<=m;i++)//前m个数可以直接进入队列，不需要考虑超出长度的问题
    {
        while(head<=top&&b[top].a>=a[i])//将队尾较大元素弹出（建立单调队列）
            top--;
        b[++top].a=a[i];//将当前元素加入队列中
        b[top].b=i;
    }
    cout<<b[head].a<<endl;//输出第一个序列中的最小值
    for(int i=m+1;i<=n;i++)
    {
        while(head<=top&&b[head].b<=i-m)//将队首已经超出序列长度的元素弹出
            head++;
        while(head<=top&&b[top].a>=a[i])//将队尾较大元素弹出（建立单调队列）
            top--;
        b[++top].a=a[i];//将元素压入队列中
        b[top].b=i;
        cout<<b[head].a<<endl;//输出当前序列最小值
    }
    return 0;
}