2 - 单调队列
准备春招,算法题冲冲冲!
单调队列
就是满足单调性的双端队列。
用数组模拟
const int N = 100010;
int q[N], hh, tt = -1;//hh为队头,tt为队尾
//插入
q[++tt] = x;
//弹出
hh++;
//判断是否为空
if (hh <= tt) 不空;
else 空;
//取出队头/尾元素
q[hh]; q[tt];
当然,也能用标准库的<deque>
。
练习题
154. 滑动窗口 - AcWing题库
如图,这是滑动窗口的过程。接下来我们要分别找滑动窗口移动时的最大值和最小值。以找最小值为例:
这时候双端队列就派上用场了,在这里它充当单调队列的角色,用于存储滑动窗口的索引(从小到大)。
随着滑动窗口的不断移动,旧元素(i)不断出队,新元素(j)不断入队。如果新元素比队尾元素还要小,为了保证队列的单调性,应先把较大的队尾元素出队后再让新元素入队。
代码如下:
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> arr(n, 0);
for (int i = 0; i < n; ++i)
{
cin >> arr.at(i);
}
// 找最小值
deque<int> q;
for (int i = 0; i < n; ++i)
{
// 滑动窗口范围[i-k+1, i]
// 旧元素出队: 检查队头索引是否已经在窗口外, 是的话就出队
if (!q.empty() && q.front() < i - k + 1)
q.pop_front();
// 新元素入队:
// - 先保证队列单调性(队尾元素必须小!)
while (!q.empty() && arr.at(q.back()) >= arr.at(i))
q.pop_back();
// - 然后新元素才能入队
q.push_back(i);
// 如果滑动窗口此时是完整的, 队头就是答案
if (i - k + 1 >= 0)
cout << arr.at(q.front()) << " ";
}
// 找最大值
q.clear();
cout << '\n';
for (int i = 0; i < n; ++i)
{
if (!q.empty() && q.front() < i - k + 1)
q.pop_front();
while (!q.empty() && arr.at(q.back()) <= arr.at(i))
q.pop_back();
q.push_back(i);
if (i - k + 1 >= 0)
cout << arr.at(q.front()) << " ";
}
}
参考资料
- 算法基础课 - AcWing