【每日一题】3月30日题目精讲 单调队列

题号 NC50528

名称 滑动窗口

来源 《信息学奥赛一本通》Part5.5

戳我进入往期每日一题汇总贴~

滑动窗口取最值问题是一个非常经典的问题，当然你可使用线段树树状数组ST表等等方法去求，我在这里呢给大家介绍一种时间复杂度，简单实在将来也有很多地方能用的方法——单调队列。

以求最大值为例：

区间的最大值为：

区间右移到后最大值为：

我们可以看到这两段区别仅仅在 和 上，扫一遍显然是很没必要的。而如果 ，那么当进入了窗口中，就不可能作为最大值存在了，如果我们记录当前区间中现在或者将来有机会成为最大值的数，那么就可以从这个记录中删掉了。如果, 当出了区间，还是有机会的，所有需要留着。

我们用一个双端队列来维护（普通的队列只能从队尾加入元素从队首删除元素，双端队列的队尾也可也删除元素），区间每次右移一个单位，首先看看队首的元素是否超出了范围，如果超出了，就把它删掉；然后将新进入区间的这个元素往双端队列里放，但放进来之前需要判断队尾（也就是还有可能成为最大值的最后一个元素）是不是小于他小于他，如果是，就把这个队尾删掉，一直到前一个元素大于等于它为止。由于我们队列里面的元素实际上是单调不增的，每次的最大实际上就在队首。而由于每个数进队和出队的次数都只有一次，时间复杂度是的。

标程是手工用数组模拟的双端队列，你也可以使用stl里的deque容器。

代码可戳我查看~

活动奖励：

在牛客博客中写出题解，并回复地址

审核通过可获得10-50牛币（依据题目难度和题解的内容而定）