单调队列基本用法

寻找各个子窗口的最大值

假如说,我们的目的是找到每一个子窗口的最大值。最简单的方法,是依次枚举所有的子窗口,
分别求出各个窗口的最大值。显然,这样的时间复杂度是O(n^2)的。其实,我们可以创建一个双端队列deque
用于维护每个窗口的可能最大值

这个队列满足一个条件,即小压大,换句话说,这个队列从队尾到队头,是严格单调递增的。

向右扩展窗口,即压入元素时,如果该元素破坏了队列的单调性,也就是说,该元素大于队尾元素,这时需要我们依次弹出小于该元素的队尾元素。
假如该元素大于队尾元素,为了找到最大值的可能性,显然,队尾元素应该弹出,让更大的元素进来。假如该元素等于队尾元素,虽然值相等,但是
该元素的坐标要更靠后,也就是说,窗口缩小的时候,该元素不容易被排除在外,更有成为最大值的可能

向右缩小窗口,即弹出元素时,此时子窗口的最大值即为队列的头部元素。

因为每个元素都只队列一次,所以时间复杂度为O(n)

例题

239. 滑动窗口最大值

给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值 。

这道题就是经典的单调队列模版题,可以参考如下解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int deque[100001];
int h, t;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
h = 0, t = 0;
int n = nums.size() - k + 1;
vector<int> ans(n, 0);
for (int r = 0, l = 0; r < nums.size(); ++r) {
// push元素进入单调队列
while (h < t && nums[r] >= nums[deque[t-1]]) {
t--;
}
deque[t++] = r;
// 满足条件则收集答案
if (r - l + 1 == k) {
ans[l] = nums[deque[h]];
// 移动左指针,更新单调队列头部位置
if (deque[h] == l) {
h++;
}
l++;
}
}
return ans;
}
};