单调队列和单调栈

单调队列

单调队列相比于一般的队列来说，多了一个队尾出队。
一般的队列是秉持先进先出的原则，所以是队尾入队，对头出队。

单调队列中的元素相比于一般队列来说，多了单调性。队列内的元素始终保持单调，即单调递减或者单调递增。

队尾出对的条件：队列不空（应对第一个加入的元素）且有新元素加入时，新元素更优。
这个新元素更优分两种情况。如果是单调递增的一组元素来说。队尾进入的元素是越小越优，也就是越小越可以排到前面。所以当元素入队之后可以使用while循环对从队尾开始的每一个元素进行判断，如果比它大就踢出队列，直到队列为空或者遇到第一个比新元素小于或者等于的元素。然后将新元素加入队列。对于单调递减的一组元素来说，这个更优的情况就是元素越大越优，越可以排到前面。

队头出队的条件是队头元素滑出窗口
例程：

#include <bits/stdc++.h>

using namespace std;
int q[1000]; 
int a[1000];
int k, n;

int main()
{
    int h = 1, t = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i <= n; i ++)
    {
        while (t >= h && a[q[t]] >= a[i]) t --;
        q[++t] = i;
        if (q[h] < i - k + 1) h ++;
        if (i >= k) printf("%d ", a[q[h]]);
    }
    return 0;
} 

单调队列是用来维护一个滑动的定长窗口内的单调序列，从队头取最值，进行计算或者转移。

单调栈是维护一个固定的变长窗口[1, i]内的单调序列，从栈顶取最值，进行计算或转移。
每个元素从栈顶入栈，淘汰元素从栈顶出栈。

淘汰的机制是和单调队列相似的，也是如果要维护一个单调递减的序列，从栈顶取的是最大值，则越大越优，维护一个单调递增的序列，从栈顶取最小值，越小越优

例程：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int a[N];
int q[N];
int ans[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    int top = 0;
    for (int i = 1; i <= n; i ++)
    {
        while (top > 0 && a[q[top]] < a[i])
        {
            ans[q[top]] = i;
            top --;
        }
        q[++top] = i;
    }
    
    for (int i = 1; i <= n; i ++)
        cout << ans[i] << ' ' ;
    return 0;
}