Solution

单调队列模板题。

具体思想：从前到后遍历序列，维护一个队列，使队列的队首一直是窗口中的最值。以最小值为例，若序列当前位置的数比队列中的队尾小，那就意味着当前位置的数贡献更大，即更有可能成为之后的最小值，于是就可以弹出队尾元素将新元素插入。注意及时从队首排除不符合范围的元素。

由于每个数至多进队列一次，出队列一次，所以时间复杂度为 。

Code

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e6+10;
int n,k,a[maxn],q[maxn][2],hd,tl;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        while(hd<=tl&&a[i]<q[tl][0])
            tl--;
        q[++tl][0]=a[i],q[tl][1]=i;
        if(q[hd][1]<=i-k)
            hd++;
        if(i>=k)
            cout<<q[hd][0]<<" ";
    }
    cout<<endl;
    hd=tl=0;
    for(int i=1;i<=n;i++){
        while(hd<=tl&&a[i]>q[tl][0])
            tl--;
        q[++tl][0]=a[i],q[tl][1]=i;
        if(q[hd][1]<=i-k)
            hd++;
        if(i>=k)
            cout<<q[hd][0]<<" ";
    }
    return 0;
}