准备春招，算法题冲冲冲！

单调队列

就是满足单调性的双端队列。

用数组模拟

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