单调队列

队列中各元素序列是严格单调递增或递减的，队首和队尾都可以出队，但入队只能从队尾入队。由于队列内元素有序，取最值的复杂度为O(1)。维护一个单调队列主要包含以下主要步骤：

1. 若队列为空，当前a[i]直接入队
2. 维护队首 队列不空，如队首超出区间范围，则队首出队
3. 维护队尾 若队列不空： 队列中所有大于等于当前a[i]的元素出队，然后a[i]入队；如队尾元素小于当前a[i]，a[i]直接入队 (单调递增队列)

1. 滑动窗口 (AcWing 154)

#include <iostream>

using namespace std;

const int N = 1e6 + 1;

int a[N], q[N];

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    int head = 0, tail = -1;
    for(int i = 0; i < n; i ++)
    {
        if(head <= tail && q[head] < i - k + 1) //维护队首，因为只滑动一个位置，所以可以用if，否则用while
            head++;
        while(head <= tail && a[q[tail]] >= a[i])//维护队尾
            tail--;
        q[++tail] = i;
        
        if(i - k + 1 >= 0)
            cout<< a[q[head]] << " ";
    }
    cout << endl;
    
    head = 0, tail = -1;
    for(int i = 0; i < n; i++)
    {
        if(head <=tail && q[head] < i - k + 1)
            head++;
        while(head <= tail && a[q[tail]] <= a[i])
            tail--;
        q[++tail] = i;
        
        if(i - k + 1 >= 0)
            cout<< a[q[head]] << " ";
    }
    
    
}