单调队列基本用法
寻找各个子窗口的最大值
假如说,我们的目的是找到每一个子窗口的最大值。最简单的方法,是依次枚举所有的子窗口,
分别求出各个窗口的最大值。显然,这样的时间复杂度是O(n^2)
的。其实,我们可以创建一个双端队列deque
,
用于维护每个窗口的可能最大值。
这个队列满足一个条件,即小压大,换句话说,这个队列从队尾到队头,是严格单调递增的。
向右扩展窗口,即压入元素时,如果该元素破坏了队列的单调性,也就是说,该元素大于队尾元素,这时需要我们依次弹出小于该元素的队尾元素。
假如该元素大于队尾元素,为了找到最大值的可能性,显然,队尾元素应该弹出,让更大的元素进来。假如该元素等于队尾元素,虽然值相等,但是
该元素的坐标要更靠后,也就是说,窗口缩小的时候,该元素不容易被排除在外,更有成为最大值的可能。
向右缩小窗口,即弹出元素时,此时子窗口的最大值即为队列的头部元素。
因为每个元素都只进和出队列一次,所以时间复杂度为O(n)
例题
给你一个整数数组
nums
,有一个大小为k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k
个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。
这道题就是经典的单调队列模版题,可以参考如下解法:
1 | class Solution { |