题号 NC50528
名称 滑动窗口
滑动窗口取最值问题是一个非常经典的问题，当然你可使用线段树树状数组ST表等等方法去求，我在这里呢给大家介绍一种时间复杂度%7D)
，简单实在将来也有很多地方能用的方法——单调队列。
以求最大值为例：
区间
的最大值为：)
区间右移到
后最大值为：)
我们可以看到这两段区别仅仅在
和 
上，扫一遍显然是很没必要的。而如果 
，那么当
进入了窗口中，
就不可能作为最大值存在了，如果我们记录当前区间中现在或者将来有机会成为最大值的数，那么就可以从这个记录中删掉了。如果
, 当出了区间，还是有机会的，所有需要留着。
以求最大值为例：
区间
区间右移到
我们可以看到这两段区别仅仅在
我们用一个双端队列来维护（普通的队列只能从队尾加入元素从队首删除元素，双端队列的队尾也可也删除元素），区间每次右移一个单位，首先看看队首的元素是否超出了范围，如果超出了，就把它删掉；然后将新进入区间的这个元素往双端队列里放，但放进来之前需要判断队尾（也就是还有可能成为最大值的最后一个元素）是不是小于他小于他，如果是，就把这个队尾删掉，一直到前一个元素大于等于它为止。由于我们队列里面的元素实际上是单调不增的，每次的最大实际上就在队首。而由于每个数进队和出队的次数都只有一次，时间复杂度是
标程是手工用数组模拟的双端队列，你也可以使用stl里的deque容器。
看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在本讨论贴中提问！
活动奖励：
在牛客博客中写出题解，并回复地址审核通过可获得10-50牛币（依据题目难度和题解的内容而定）
本道题目4月6日中午12：00之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
全部评论
(47) 回帖