题解报告：P1886 滑动窗口 /【模板】单调队列（单调队列）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
int a[maxn];
deque<int >m1;
int main()
{
    int n,k,i,j;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++){
        while(m1.size()&&a[i]<a[m1.back()]){
            m1.pop_back();
        }
        m1.push_back(i);
        while(i-k>=m1.front()){
            m1.pop_front();
        }
        if(i>=k)
        printf("%d ",a[m1.front()]);
    }
    printf("\n");
    m1.clear();
    for(i=1;i<=n;i++){
        while(m1.size()&&a[i]>a[m1.back()]){
            m1.pop_back();
        }
        m1.push_back(i);
        while(i-k>=m1.front()){
            m1.pop_front();
        }
        if(i>=k)
        printf("%d ",a[m1.front()]);
    }
    return 0;
}