AcWing 154. 滑动窗口(单调队列)

题目描述

---

本题强推b站 董晓算法 老师的讲解，通俗易懂，我也是借鉴了里面许多关键思想。9.74 单调队列 滑动窗口最大值——信息学竞赛培训课程

---

分析：

滑动窗口可以先考虑暴力解，对长度为 $m$ 的窗口。构建一个模型，利用双指针，$i$ 指针为外层循环指针，$j$ 为内层循环指针，对窗口内的元素的下标进行循环。如下：

计算窗口最小值需要 $O(m)$，移动 $n-m+1$ 次，总时间复杂度为 $O(nm)$。
代码为：

for (int i = m; i <= n; i ++)
{
	int mi = a[i];
	for (int j = i - m + 1; j <= i; j ++)
	{
		mi = min(mi, a[j]);
	}
	printf("%d ", mi);
}

1
2
3
4
5
6
7
8
9
10

接下来我们使用单调队列来对问题进行优化，那么我们先看什么是单调队列，如何构造单调队列，以及为什么要用单调队列。

我们先考虑滑动窗口中的最大值问题。

单调队列：队列内的元素值是单调的，递增或递减。本题用单调队列存储当前窗口内单调递减的元素，并且队头是窗口内的最大值，队尾是窗口内的尾元素。也就是说，队列从队头到队尾对应窗口内从最大值到尾元素的一个子序列。

1. 队头出队：当队头的元素从窗口滑出时，队头元素出队(head ++)；
2. 队尾入队：当新元素滑入窗口时，要把新元素从队尾插入，分两种情况：
   ① 直接插入：如果新元素小于队尾元素，那就直接从队尾插入(++ tail)，因为它可能在前面的最大值滑出窗口后成为最大值。
   ② 先删后插：如果新元素大于等于队尾元素，那就先删除队尾元素(因为它不可能称为窗口中的最大值，新来的就比它大)，删除方法是 tail --，即从队尾出队。循环删除，直到对空或遇到一个大于新元素的值，插入其后(++ tail)。

这样做，每次都能从队头取得窗口中的最大值。如何判断队头元素何时出队呢？当我们在队列中存储的是元素值时，这是很难判断的，但若存储的是该元素所对应的下标值就容易判断了：可根据 $i$ 和队头元素的下标的差与窗口大小进行比较。

由于每个元素最多进队和出队各一次，因此该算法的时间复杂度为 $O(n)$。

---

代码(C++)

#include 

using namespace std;

/*
求最大值时，用单调队列存储当前窗口内单调递减的元素，队头是窗口内的最大值，队尾是窗口内的尾元素。
求最小值时，用单调队列存储当前窗口内单调递减的元素，队头是窗口内的最小值，队尾是窗口内的尾元素。
*/
const int N = 1000010;
int a[N], que[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    
    for (int i = 0 ; i < n; i ++) scanf("%d", &a[i]);
    int head = 0, tail = -1;
    
    for (int i = 0; i < n; i ++)
    {
        // 一旦 que[head] 不在 [i-k+1,i] 中，队头出队
        if (head <= tail && i - k + 1 > que[head]) head ++;
        
        // 若当前值小于等于队尾元素时，则队尾元素不可能称为窗口最小值
        // 则将队尾元素出队
        while (head <= tail && a[que[tail]] >= a[i]) tail --;
        
        // 下标入队，便于队头出队，方便处理下一个滑动窗口
        que[++ tail] = i;
        
        // 使用队头中的最小值
        if (i >= k - 1) printf("%d ", a[que[head]]);
    }
    puts("");
    
    // 求窗口最大值情况相似
    head = 0, tail = -1;
    for (int i = 0; i < n; i ++)
    {
        if (head <= tail && i - k + 1 > que[head]) head ++;
        while (head <= tail && a[que[tail]] <= a[i]) tail --;
        que[++ tail] = i;
        
        if (i >= k - 1) printf("%d ", a[que[head]]);
    }

}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

---