单调队列
这个技巧和单调栈一样,运用的场景比较少
它本质也是一个队列,只不过是运用了一些巧妙的逻辑
在内部维护了一个递增或者递减的序列
然后还保持了先进先出的特性
下面直接看题
滑动窗口最大值
这道题的描述不就是使用滑动窗口技巧吗,我们知道在滑动窗口技巧中
最重要的就是清楚在何时扩大窗口,在何时缩小窗口
但是这道题中,我没法根据出窗口的那个元素来判断是否需要更新最大值,如何更新
如果出窗口的就是最大值,那我就需要重新遍历一遍窗口找到最值,这样的时间复杂度是较高的
所以就需要使用到单调队列的技巧了
这里我们自己维护一个单调队列的类
1 | public class MonotonousQueue { |
在队尾添加元素的时候,需要将所有队尾元素比它小的元素都出队,直到遇到第一个比它大的元素或者队列为空的时候
最大值就是队列的队首元素
下面看这道题的解法
1 | class Solution { |