单调栈与单调队列

很经典的两个问题，但是最初学习的时候很不认真，以至于后面遇到相似的问题想不起来这两个模板。

单调栈

给定一个长度为 N 的整数数列（>0），输出每个数左边第一个比它小的数，如果不存在则输出 −1。

维护一个单调栈，按照当前题意即使保证栈内的单调性是单调升。

初始我们可以让 -1 入栈，因为要求的是左边第一个小的数，且不存在就输出 -1 。

然后我们就可以遍历这个整数数列，对每一个数，执行如下操作:

1. 从栈顶开始，如果栈顶数大于等于当前这个数，那么排除
2. 持续操作1，知道栈顶的数小于当前数
3. 将当前数放到栈顶，并记录

stl写法

int n;
cin>>n;
while(n--)
{
    int x;
    cin>>x;
    while(t && stk[t] >= x) t--;
    if(!t) cout<<-1<<" ";
    else cout<<stk[t]<<" ";
    stk[++t] = x;
}

模拟栈写法：

int top = 0;
a[0] = -1;
stk[++ top] = 0;
for(int i = 1; i <= n; i ++)
{
    cin>>a[i];
    while(a[stk[top]] >= a[i]) top --;
    ans[i] = a[stk[top]];
    stk[++ top] = i;
}

单调队列

和单调栈有不同之处，比如滑动窗口的题目，如果要我们求窗口内的最大值，那么我们队列维护的应该是一个单调减的区间，因为如果出现增的话，那么这个最大值前面的最小值都可以删去，因为窗口是不断向后滑动的，那么前面小的永远不可能再次使用到。

因此和单调栈类似，while排出所有小于的值，然后插入当前值。

判断队列的队首是否出窗口，可以使用