【写在前面】
单调队列，可以以优秀的时间复杂度解决队列中的最值问题，常用来优化一类单调的DP问题，是一些更加高级的优化方法（如斜率优化）的基础。
【问题引入】
考虑这样一个问题，给你一个队列，支持在队尾添加元素，在队首删除元素，要求时刻维护该队列中的最大值。
显然我们可以使用 优先队列/平衡树 等数据结构来解决这个问题，但是编程复杂度略高，且时间复杂度上要多出一个log，还会带来较大的~~万恶~~常数。
有这样一种优美的数据结构，她借助一个时刻保持单调辅助队列，其队首元素始终是原队列的最值，可以做到$O(1)$询问，插入删除共计时间复杂度$O(n)$，这就是我们今天的主角——单调队列。
【单调队列】
以最大值为例，我们设原队列为Q，辅助队列为aux。
插入 ->
记要插入队尾的元素为x。
首先将元素x插入到Q的队尾，接着，考虑维护aux的单调性，从aux的队尾向前，将所有 小于 x 的元素全部删除，然后再将x插到aux的队尾。
为什么这些元素会被无情的删除呢？因为它们小于x，所以只要x在队列中，这些元素就绝不可能成为最大值，而它们是在x之前入队的，所以必然在x之前出队，所以它们无论如何都不可能成为最大值，故可以放心删除。
形象的说，在队列中它们会一直受到 x 的 "压迫" ，而又等不到 x "离去"的那一天，因此不如趁早离开。
这实际上是去除了冗余的元素，如果应用在DP中，就是去除冗余的状态。
删除 ->
记当前Q的队首元素，即将要删除的元素为x。
将x与aux的队首元素比较，如果相等，说明要删除的元素是当前队列的最大值，所以在删除Q的队首元素x后，也要删除aux的队首元素，使原来的次大值成为最大值~~（翻身啦）~~。
【时间复杂度】
询问是$O(1)$的（直接取aux队首元素即可），因为每个元素至多被删除一次，故所有插入删除的总时间复杂度是$O(n)$的
【实质】
辅助队列上实质是维护了原队列的一个在元素值和下标上均单调的一个子序列。
【代码实现】
实现上，借助了STL中的deque双端队列，编程复杂度很低。
template <typename Item> struct MonotonicQueue{
std::deque<Item> data, aux;
void push(const Item &x){
data.push_back(x);
while(!aux.empty() && aux.back() < x) aux.pop_back();
aux.push_back(x);
}
void pop(){
if(data.front() == aux.front()) aux.pop_front();
data.pop_front();
}
size_t size(){
return data.size();
}
Item max(){
return aux.front();
}
}
【应用】
单调队列常用于优化形似这样的DP: $$f[i] = max\{\ g(k)\ \} \ k \in [l(i), r(i)] + w(i)$$ 其中$l(i)，r(i)$均是随 $i$ 的增加而单调不减的。 并且$g(k)$的值是与$i$无关的，只和$k$有关。
有些DP原本的方程并不是这个形式，但经过一定变形是可以成为这种形式的。
常用的手段是当要求最值的项与$i$相关时，想办法将其提出来。
【例题】
传送门-> 烽火传递 - 单调队列优化DP
就是这样啦