队列
简介 #
队列是一种「先进先出」的数据结构.元素从队列的前端进入（入队），从末端离开（出队），类似于排队.基本操作见 STL Queue.
双向队列 #
队列元素只能从一端进，另一端出，有时无法满足问题的需要.双向队列应运而生，它支持从两端插入或删除元素.
双向队列的基本操作见 STL Deque.
单调队列 #
单调队列的元素从队头到队尾满足单调性，适用于查询某一动态区间的最大（或最小）元素.
插入元素 #
将 $A[i]$ 入队，维护队列单调性，同时保证队列元素在 $A[p\cdots i]$ 范围内.以单调递增队列为例：
-
重复弹出队头，直到队头 $≥p$；
-
重复弹出队尾，直到 $A[$队尾$]<A[i]$（若单调递减，则重复直到 $A[$队尾$]>A[i]$）.
-
将 $i$ 入队.
涉及双端操作，须使用双向队列.此时 $A[p\cdots i]$ 范围内最小元素为 $A[$队头$]$.
deque<int> q; // 存储元素下标
void insert(int i, int p) { // 将 a[i] 入队，维护队列元素在 a[p...i] 范围内
while(!q.empty() && q.front() < p) q.pop_front();
while(!q.empty() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
}滑动窗口 #
一个滑动窗口（长度为 $k$）从数组 $A$ （长度为 $n$）的左端移动到右端，每次只向右移一位.求每次滑动时窗口区中的最大值.
示例（$k=3,n=8$，红色数值在窗口区内）：
| $A_1$ | $A_2$ | $A_3$ | $A_4$ | $A_5$ | $A_6$ | $A_7$ | $A_8$ | 最大值 |
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 7 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 7 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 7 | 5 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 7 | 5 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 7 | 6 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 7 | 7 |
朴素算法 #
枚举 $i=k\rightarrow n$，枚举出区间 $[i-k+1,i]$ 中的最大整数.时间复杂度为 $O(nk)$.
for(int i = k; i <= n; i ++) {
int maxn = a[i];
for(int j = i - k + 1; j <= i; j ++)
maxn = max(maxn, a[j]);
cout << maxn << ' ';
}单调队列优化 #
使用单调递减队列优化「查找区间 $[i-k+1,i]$ 中的最大整数」的效率.时间复杂度为 $O(n)$.
deque<int> q;
void insert(int i, int p) {
while(!q.empty() && q.front() < p) q.pop_front();
while(!q.empty() && a[q.back()] <= a[i]) q.pop_back();
q.push_back(i);
}
for(int i = 1; i <= n; i ++) {
insert(i, i - k + 1);
if(i >= k) cout << a[q.front()] << ' ';
}