一、浅谈单调队列

单调队列优化，一种将线性dp从 O(n2) 优化到 O(n) 的优化技巧。

具体而言是维护队列中的单调性，最终达到得出单调最值的目的。

但通过条件状态的设计可以在线性dp中起到很好的效果。

二、实现方法

（1）可以选用STL库的 deque 双端队列来实现。

不过维护起来不是很方便，一般建议是手写双端队列，便于调试。

（2）可以手写双端队列。定义一个数组用于模拟队列，

再以 head 和 tail 两个变量对队头和队尾进行维护，不断出队入队。

示例如下：

int head=0,tail=0;
int que[N];
for(int i=1;i<=n;i++)
{
	while(tail-head>k&&tail>head)head++;
	while(que[tail]<a[i]&&tail>head)tail--;
	que[++tail]=a[i];
}
printf("%d",que[head]);

在以上代码中，我们维护了一个宽度为 k 的区间内的最大值，

通过这种方法，我们可以在扫完 n 个数的同时得出结果。

不难看出队列是满足单调性的。

三、复杂度证明

毋庸置疑， O(n) 的复杂度是单调队列优化的一大优势。

观察上面的示例代码，可以发现tail≥head 始终成立，

而关注 head 则会发现， head 具有单向性，只会不断向队尾靠近。

因此在更新的过程中，每次最多只会使得 tail+1 ,

而 head 扫完的复杂度正是 O(n) 。

四、注意事项

之前提到过单调队列优化需要答案满足单调性，

但这并不意味着优化对象需要满足。

也就是说，哪怕扫的数列不满足单调性，

但只要求的答案是满足单调性的就可以使用。

之前一直不理解单调队列的原理和使用条件，但是后来看了一篇博客，里面举了个很生动的例子，让我一下子就悟了：新高一OIer一进来就比新高二和新高三的都要强，那么新高二新高三的就可以直接当场退役了。