单调队列，就是单调的队列，通常用来解决滑动窗口的最值问题，可以应用到 DP 的优化上。一个单调队列中的元素总是单调递增（或递减）的。
滑动窗口
例：有一个队列，每次从队尾加入一个元素，或从队首删除一个元素，并在任何时刻求整个队列的最大值。
一个很直接的想法是使用优先队列 priority_queue 即堆，堆可以在 的时间内求出最大值，但每次加入或删除时需要 的时间完成堆的调整，但是用了堆后就不能按照进队的顺序出队了！这时候你可以大胆地写一个平衡树或者 set——如果你不怕多出来的 和平衡树常数带来的 TLE 的话。
单调队列就是解决这类问题的数据结构，我们用一个辅助队列，使该队列的首元素总是原队列的最大值，这样就可以 地求出队列的最大值了。
维护单调队列
现有需要维护最大值的队列 Q，和辅助队列 M，设计算法使任何时刻时 M 队首元素都是当前 Q 的最大值。
每次在 Q 的队尾加入元素 x 时，也将其加入到 M 中，从 M 的队尾向前遍历，将遍历到的所有 小于等 x 的元素全部删除，因为它们在 x 之前被加入到队列中，在 x 出队前它们就已经都出队了，即在 x 出队前这些元素不可能成为队列中的最大值。
每次在 Q 的队首删除元素时，将要删除的元素与 M 的队首元素比较，如果该元素与 M 队首元素相等，即该元素为执行删除操作前队列的最大值，则同时也要将 M 的队首元素删除，使原 Q 的次小值成为 M 的队首元素，保证 M 的队首元素是删除操作后 Q 中最大的元素。
应用
状态转移方程形如 的动态规划可以使用单调队列来优化。
实现
因为同时要从队列的两端添加、删除，所以要使用 deque 实现，而不是 queue。
template <typename T>
struct MonotoneQueue {
std::deque<T> q, m;
void push(const T &x) {
q.push_back(x);
while (!m.empty() && m.back() < x) m.pop_back();
m.push_back(x);
}
void pop() {
T x = q.front();
q.pop_front();
if (x == m.front()) m.pop_front();
}
size_t size() {
return q.size();
}
T top() {
return m.front();
}
};