单调队列

单调队列的基本思想是，维护一个双向队列（deque），遍历序列，仅当一个元素可能成为某个区间最值时才保留它。

一般在对头放最大值或者最小值。

基本流程（以最小值为例）：滑动窗口遍历数组，从队尾放入数据，若队列中从队尾到对头有比该数大的数，则弹出。在滑动窗口移动过程中，若pre指针（滑动窗口前向指针）指向的数==队头元素，则该次滑动窗口移动之后弹出队头元素。

例子：附近最小 - 蓝桥云课 (lanqiao.cn)

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
#include <iostream>
#include <vector>
#include <deque> //双端队列
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n + 1, 0);
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

	int k;
	cin >> k;
	//滑动窗口、单调队列

	deque<int> deq;

	for (int back = 1; back <= n + k; back++) //从back位置开始一个个扫描添加到双端队列中
	{
		int pre = back - 2 * k;

		if (back <= n)
		{
			while (!deq.empty() && deq.back() > a[back])
			{
				deq.pop_back(); //尾部大于当前添加的就弹出去
			}
			deq.push_back(a[back]);
		}

		if (pre - 1 >= 1 && !deq.empty() && deq.front() == a[pre - 1]) //用上一次的指向来进行对比，为什么不用该次呢？因为该次pre指向元素还在窗口内。
		{
			deq.pop_front();
		}
		if (back > k) //但是需要back到达初试位置（即1+k）之后，再进行最小值的输出
			cout << deq.front() << " ";
	}
}

以最大值为例的视频讲解：单调队列正式登场！| LeetCode：239. 滑动窗口最大值_哔哩哔哩_bilibili