单调栈

单调栈是满足单调性的栈结构。

举例说明：

当向栈中插入元素时，为了维护栈的单调性（单调递增），需要弹出一些元素，而弹出元素的数目应该是最小的，之后再将元素插入到栈顶。

例如，栈中目前有元素 $\{21,15,7,0\}$，之后我们插入元素 $12$ 则需要依次弹出元素 $0,7$ 此时栈变为 $\{21,15,12\}$。

// 插入元素 x
stack<int> stk;
while (stk.size() && stk.top() <= x) {
	stk.pop();
}
stk.push(x);

单调队列

问题：

给定长度为 $n$ 的整数数组，求每连续 $k$ 个元素中的最大值和最小值？

暴力想法自然是两重循环，枚举每 $i\sim i+k-1$ 的子段，求出其最大值和最小值，时间复杂度为 $O(n\times k)$。当 $k$ 较大时，显然会 TLE。

此时可以使用单调队列。

单调队列指的是队列中的元素满足单调递增或单调递减的性质。

例如我们维护一个单调递增队列 $Q=\{\}$，初始为空，且 $k=3$。

有如下序列：

$213015747307699$

操作如下：

操作	结果
$21$ 入队	$\{21\}$
$30\ge 21$，$30$ 入队	$\{21,30\}$
$15\le 30\mathrm{\&}15\le 21$，$15$ 入队，$30,21$ 出队	$\{15\}$
$7\le 15$， $7$ 入队 $15$ 出队	$\{7\}$
$47\ge 7$，$47$ 入队	$\{7,47\}$
$30\le 47$，$30$ 入队，$47$ 出队	$\{7,30\}$
此时 $7$ 已在窗口外，$7$ 出队，$76\ge 30$，$76$ 入队	$\{30,76\}$
$99\ge 76$，$99$ 入队	$\{30,76,99\}$

总结，单调队列每一次操作遵循以下流程：

1. 第一步从队头开始清理已不在窗口的元素
2. 第二步从队尾开始清理不满足单调性质的元素
3. 第三步将元素入队