单调队列和单调栈
我所认为的单调队列就是单调栈+取操作。
刚开始学单调栈的时候，翻开一篇单调栈的博客就能看到单调队列。后来才发现单调队列=单调栈+取栈底(出栈底)
单调栈
什么是单调栈？
来自某b乎：
单调栈是一种理解起来很容易，但是运用起来并不那么简单的数据结构。 一句话解释单调栈，就是一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性。
栈这样的数据结构满足先进后出。假设一个数组从左到右依此进栈和出栈操作，我们令数组元素的值等于它在数组中的下标。那么在这个过程中栈中元素始终满足栈底到栈顶的下标递增。
而单调栈是在栈的基础上有栈底到栈顶满足一定的单调性。
单调栈的性质是什么？
经过前面描述，我们可以知道，单调栈满足该栈中栈底到栈顶元素的id递增且元素满足一定的单调性
而且必须保证随着时间的推移，栈内元素还满足单调栈的性质。
数组中的元素只能进栈和出栈至多一次。所以时间复杂度为O(n)
用到单调栈的场景？
说实话用到的都是单调的性质，一般都是用单调队列。
给你一个数组S。数组T的值 Ti=min(Sk)k∈(pi,i),其中 pi小于 i,且满足随着 i的增大 pi不减小。
比如洛谷的滑动窗口题目
单调队列
如果把一个单调栈的栈底看作单调队列的队首，单调栈的栈顶看作单调队列的队尾，那么这个新的数据结构就是单调队列了。
单调队列与普通的队列有些不同，单调队列支持从队首删除，队尾添加和删除，故单调队列多使用deque实现。
插入操作：
将元素插入单调队列中总是与队尾的元素比较，队尾元素不是更优就将队尾元素删除，直到队列为空或该元素没队尾元素优，就将该元素加入队列。
取操作：
当需要取的时候就从队首取元素，如果队首元素的id不在要求的范围内就删除队首元素，然后再次进行取操作。
要求：
而且必须保证随着时间的推移，栈内元素还满足单调栈的性质。
下面举一些例题：
洛谷的滑动窗口：传送门
2019计蒜之道复赛D题 “星云系统”：传送门
HDU - 3706 Second My Problem First :传送门
HDU3530 Subsequence 单调队列:传送门
HDU-4122 Alice’s mooncake shop :传送门
京公网安备 11010502036488号