单调队列/栈

单调栈和队列的思路:
删除无效的元素，使得整个数据结构有序

单调队列和单调栈如何取决：如果要用到的数据结构有涉及到一个区间的长度，那么使用单调队列会更好，因为它的头和尾都可以操作，可以更好的控制它的长度。如果使用栈的话，只有一个操作的地方，不方便控制。

#include "iostream"

using namespace std;

const int N = 1e6 + 10;

int n;
int stk[N], tt;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x)
            tt--;
        if (tt)
            cout << stk[tt] << ' ';
        else
            cout << -1 << ' ';
        stk[++tt] = x;
    }
    cout << endl;
    return 0;
}

#include "iostream"

using namespace std;

const int N = 1e6 + 10;

// a为数组 q为模拟的单调队列的下标
int a[N], q[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    // 求最小的
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        // 判断队列是否为空&&队头是否已经滑出窗口（用下标来判断）
        // q[hh]一直存储的是最小值的下标，所以当i-k+1>q[hh]时即已经积累了超过三个最小值递增
        // i-k+1就是从i处向前的k个元素，q[hh]为目前队列中的最小值的位置，在这种情况下就是
        // q[hh] i-2 i-1 i 这种情况 所以需要将hh++让他符合题目长度为k的窗口中的最小值
        if (hh <= tt && i - k + 1 > q[hh])
            // 从队头弹出一个数
            hh++;
        while (hh <= tt && a[q[tt]] >= a[i])
            // 出队
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d", a[q[hh]]);
        puts("");
    }
    puts("n");

    // 求最大的
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        // 判断队列是否为空&&队头是否已经滑出窗口（用下标来判断）
        if (hh <= tt && i - k + 1 > q[hh])
            // 从队头弹出一个数
            hh++;
        while (hh <= tt && a[q[tt]] <= a[i])
            // 出队
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d", a[q[hh]]);
        puts("");
    }
    puts("n");

    return 0;
}