单调队列单调栈

单调队列，用来维护给定大小区间的最值。并且队列中元素之间的关系具有单调性，而且，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。
可以用来维护给定区间的最大（最小值）（滑动窗口）

单调栈，用来维护最近的大于/小于关系，可以维护偏向全局的大小关系。

单调队列实现

去尾操作

用来维护队列的单调性，当有新元素需要入队时，从队尾向前依次移除影响单调性的元素。操作结束后，进行入队。

删头操作

用来维护求解区间，当头部元素不在要求求解的区间里时，对头部元素进行删除。

取解操作

当进行完上面两步的操作后，那么队头元素即为该区间的极值。

队列中存的是下标。

实现形式

STL

双向队列

deque<int>que;
pop_front()
pop_back()

等方法删头去尾

手写

定义一个长数组

int a[maxn];//队列
int head,tail；//队列指针

单调栈实现模板

stack<int> s;
for (遍历这个数组)
{
		//当判断是栈顶元素小于当前元素为单调递减栈，相反为单调递增栈
		while (栈不为空 && 栈顶元素小于当前元素)
		{
			栈顶元素出栈;
			更新结果;
		}
		当前数据入栈;
}

单调队列实现模板

deque<int>dq;
    for(int i=0;i<n;i++)
    {
        if(!dq.empty()&& dq.front() <i-k+1)//最前方元素是否超出范围
        {
            dq.pop_front();
        }
        while(!dq.empty() && a[dq.back()]>=a[i])//维护某种单调性
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if(i>=k-1) //下标是否达到所需数量。
        {
            printf("%d ",a[dq.front()]);
        }