数据结构基础-单调队列

单调队列 - xiongyuqing - 博客园 (cnblogs.com)

字面意思：队列是单调的，根据题目要求队列保持单调减或单调增，用以优化某种问题

如果我们要求每一个滑动窗口内的最大值和最小值，对于一个长度为 n 的序列，窗口大小为 k 来说，暴力做法为：

枚举每一个窗口，遍历每一个窗口的值取最大值或最小值

for(int i = k - 1;  i < n; ++ i)
{
    ans = a[i];
    for(int j = i; j > i - k; --j)
    {
        ans = max/min(ans, a[j]);
        ...;
    }
}
           

但是我们发现有些数字在以后的求解过程中是永远不会被当成答案的

例如，如果在求滑动窗口内的最小值时，可以发现当窗口从左往右滑动的过程中，如果当前新进来的当前值，比原始滑动窗口中的某些值小，那么对于以后要求解的窗口而言，这些相对于当前值大的某些值是不可能被当成答案的，因为当前值更靠右且更小。

于是每来一个新值，都会从队尾到队头与每一个队列中的元素比较，将比自己大的或者等于的值弹出，那么只有比队内元素都大的值才会存入队列中，于是队列中的元素都是单调递增的

具体的算法：

• 每新来一个当前值，判断滑动窗口队列是否已满，如果已满则从队首弹出一个值
• 从队尾到队首依次与当前值比较大小，如果比当前值大则从队尾弹出
• 将当前值插入队尾
• 输出队首元素的值即为答案

例如下面的序列：

1 3 -1 -3 5 3 6 7

序列长度为 8 ，窗口大小为 3

1. 队列未满，首先 1 入队列；队列元素：1
2. 队列未满，新来元素 3 与队尾元素 1 比较，3 更大，3 入队列；队列元素：1 3
3. 队列未满，新来元素 -1 与队尾元素 3 比较，-1 更小，3 从队尾弹出，-1 与队尾元素 1 比较，-1更小，1 从队尾弹出，-1 入队列；队列元素：-1；此时以遍历完一个窗口大小的元素数量，第一个窗口的最小值已产生为队首元素 -1
4. 队列未满，新来元素 -3 与队尾元素 -1 比较， -3 更小，-1从队尾弹出；队列元素：-3，答案 -3
5. 队列未满，新来元素 5 与队尾元素 -3 比较，5 更大，从队尾插入，队列元素：-3 5，答案：-3
6. 队列未满，新来元素 3 与队尾元素 5 比较，3 更小，5 从队尾弹出，3 与队尾元素 -3 比较，3 更大，从队尾插入；队列元素：-3 3，答案：-3
7. 队列未满，新来元素 6 与队尾元素 3 比较，6 更大，插入队尾；队列元素：-3 3 6，答案：-3
8. 队列已满，从队首弹出元素 -3，队列元素：3 6；新来元素 7 与队尾元素 6 比较，7 更大，插入队尾；队列元素：3 6 7，答案：3

同理对于求滑动窗口的最大值，那么左边比新来的当前值小的数就不可能成为后面的答案，于是队列中是单调递减的

例题

154. 滑动窗口 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 1e6 + 5;
int q[N], a[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++ i) scanf("%d", &a[i]);
	int hh = 0, tt = -1;
    for(int i = 0; i < n; ++ i)
    {
        if(hh <= tt && i - k + 1 > q[hh]) ++hh;
        while(hh <= tt && a[q[tt]] >= a[i]) --tt;
        q[++tt] = i;	// 注意这里存的是下标，而不是具体的值，这是为了判断是否队列满了
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    printf("\n");
    
    hh = 0, tt = -1;
    for(int i = 0; i < n; ++ i)
    {
        if(hh <= tt && i - k + 1 > q[hh]) ++hh;
        while(hh <= tt && a[q[tt]] <= a[i]) --tt;
        q[++tt] = i;	
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    return 0;
}