滑动窗口

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N];
int hh = 0, tt = -1;

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        if(hh <= tt && q[hh] < i - k + 1)hh ++;
        while(a[q[tt]] >= a[i] && hh <= tt)tt --;//保证整个队列是单调递增的，这样队头元素就是最小值
        q[++ tt] = i;
        if(i >= k)cout << a[q[hh]]<<" ";
    }
    puts("");
    
    hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++)
    {
        if(hh <= tt && q[hh] < i - k + 1)hh ++;
        while(a[q[tt]] <= a[i] && hh <= tt)tt --;
        q[++ tt] = i;
        if(i >= k)cout << a[q[hh]]<<" ";
    }
    return 0;
}