算法板子：滑动窗口——应用单调队列，找到窗口中的最小值与最大值

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N];
// q数组模拟单调队列; q数组存储原数组元素的下标; 
// 递增单调队列的队头始终维护窗口中的最小值; 队头存的是窗口中最小值的下标
// 递减单调队列的队头始终维护窗口中的最大值; 队头存的是窗口中最大值的下标
int q[N], hh, tt = -1;

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    
    // 找窗口中最小值
    for (int i = 0; i < n; i ++ )
    {
        // 队头始终维护当前窗口最小值，如果队头已经不在窗口中，将队头移出队列
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
        // 队列必须是单调递增的，新加入队列的元素的值得比队尾的值大
        while (hh <= tt && a[i] <= a[q[tt]]) tt -- ;
        // 窗口中每加入一个新元素，队列需要加入该元素的下标
        q[ ++ tt] = i;
        
        // 当窗口长度满足题目条件时，输出每个窗口的最小值，由队头维护
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    printf("\n");
    
    // 清空队列，重新维护一个递减单调队列
    hh = 0, tt = - 1;
    // 找窗口中的最大值
    for (int i = 0; i < n; i ++ )
    {
        // 队头始终维护当前窗口最大值，如果队头已经不在窗口中，将队头移出队列
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
        // 队列必须单调递减，新加入队列的元素的值需要比队尾元素的值小
        while (hh <= tt && a[i] >= a[q[tt]]) tt -- ;
        // 向队列中加入新元素的下标
        q[ ++ tt] = i;
        
        // 当窗口长度满足题目条件时，输出每个窗口的最大值，由队头维护
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    
    return 0;
}