题目描述

假设塔子哥是一家电子产品公司的CEO，他的公司生产了 $N$ 个产品。

由于市场竞争激烈，塔子哥决定评选出最差的产品，并对其进行改进。评选的方式是首先对每个产品进行评分，然后根据评分区间计算相邻几个产品中最差的产品。

题目思路

滑动窗口的基础题，思想就是用单调队列维护一个窗口，每次的答案就是队列的第一个

本题单调队列维护的是一个严格单调递增的队列

原理：试想，窗口为M大小在滑动时，每次的答案就是窗口内的最小值，但如果暴力判断的话时间复杂度将会是O(NM)。仔细思考我们可以用发现其实窗口内有些值是不用保存的，例如窗口大小为3，序列为[3, 4, 1, 2, ....]，可以看到一开始的窗口覆盖的是[3, 4, 1]，我们发现只要有1在，4是不可能再未来成为最差的那一个，3也是同理，因为有比他更差的，并且下标还是比他靠后的，固我们其实只要保存最小值1便可。再往后想，经过一次滑动后窗口覆盖的是[4, 1, 2]，同理4是不用保存的，但2是有必要保存的，因为2虽然比1要大，但其下标却靠后，窗口在滑动时1离开了窗口后，2可能便是窗口的最小值，固对于这种情况，2是需要保存下来的，固此时需要保存[1,2]便可。如此分析可以看出单调队列维护的是一个严格单调递减的队列。

具体单调队列的实现是用双端队列，在队头取出当前窗口的最小值，同时如果说当前队头的最小值已经准备离开窗口则需要弹出队列，在队尾负责维护队列是单调的，即在队尾弹出比当前元素要大的值并且插入队伍