题目

对于一个长度为 n 的数组，有长度为 m(m ≤ n)的滑动窗口，要求滑动到每一个点时，窗口区域内的最（大/小）值。

解题

如果使用暴力，在每一段之内求max，那么时间复杂度为O(m*n)

而使用单调队列算法，可以在O(n)内解决该问题

数据结构

算法维护了一个下标对应的元素单调增减的队列（是的，q里存的是数组下标）

求最小值时要求单调递增；求最大值时则要求单调递减（是不是有点反直觉）

核心思想（我理解的）是判断元素是否有成为最值的潜力

以上题目的解题代码和注释如下：

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
if __name__ == '__main__':
    # 读取 数组长度n 窗口长度k
    n, k = map(int, input().split())
    # 读取 输入的数组啊
    a = list(map(int, input().split()))

    # 下面我们先来求最小值

    # 维护一个单调队列
    q = [0 for i in range(n)]
    # 初始状态t是-1，后面会>=h，入队列是从尾部tt入
    hh, tt = 0, -1
    for i in range(n):
        # 窗口开始滑
        # 如果窗口的头部滑走了，队列的首元素不再包含在窗口中，那么出队列
        if hh <= tt and q[hh] < i - k + 1:
            hh += 1
        # 接下来开始考虑，滑动窗口中纳入的这个新元素，和队列中的老元素的关系
        # 例如，我们现在在求最小值，那么如果新元素更小，那么老元素就“没有在未来成为最小值的潜力”
        # 因此我们需要把老元素排出队列
        while hh <= tt and a[q[tt]] >= a[i]:
            tt -= 1
        # 窗口纳入的这个新元素，在这一轮一定是被认为有潜力的（老的都走光了他就上位了）
        # 所以他一定入队列
        tt += 1
        q[tt] = i

        # 因为从i=k-1开始，窗口大小才正式进入数组中，从此开始我们取最值
        # 最值就是我们的队首元素（单调递增嘛）
        if i >= k - 1:
            print(a[q[hh]])

    # 下面用同样的方式求最大值
    hh, tt = 0, -1
    for i in range(n):

        if hh <= tt and q[hh] < i - k + 1:
            hh += 1

        while hh <= tt and a[q[tt]] <= a[i]:
            tt -= 1
        tt += 1
        q[tt] = i

        if i >= k - 1:
            print(a[q[hh]])