单调队列简述

【模板】单调队列 / 滑动窗口

如果一个选手比你小还比你强，你就可以AFO了。

本题是一道单调队列的模板题。

首先澄清一下什么是单调队列。

顾名思义，单调队列的重点分为单调和队列。

单调指的是元素的规律——递增（或递减）。

队列指的是元素只能从队头和队尾进行操作。

——OI-Wiki

但是，单调队列的队列又和普通的队列不一样。

普通的队列是FIFO的，也就是说只能从队头入队，从队头出队。

单调队列的队列是双端队列。

双端队列是什么意思呢？

双端队列的队头和队尾都可以出队及入队。

---

好，说完单调队列的队列和普通的队列的区别，再说一说单调。

换个方法讲，当序列$r$满足以下条件时，就可以成为单调的：

1. $\forall i,0<i<|r|,r_i<r_{i+1}$（单调递增）；
2. $\forall i,0<i<|r|,r_i\le r_{i+1}$（不严格单调递增）；
3. $\forall i,0<i<|r|,r_i>r_{i+1}$（单调递减）；
4. $\forall i,0<i<|r|,r_i\ge r_{i+1}$（不严格单调递减）。

---

解释完单调队列，再来讲这道题。

当我们不知道单调队列时，我们会用$O(nm)$的时间复杂度来写这道题：

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int n, m, r[1000006], s[1000006];
int main()
{
    cin >> n >> m;
    for (int i{1}; i <= n; i++)
        cin >> r[i];
    for (int i{1}; i + m <= n + 1; i++)
    {
        int a{r[i]}, b{r[i]};
        for (int j{i + 1}; j < i + m; j++)
            if (r[j] > a)
                a = r[j];
            else if (r[j] < b)
                b = r[j];
        cout << b << ' ';
        s[i] = a;
    }
    cout << endl;
    for (int i{1}; i + m <= n + 1; i++)
        cout << s[i] << ' ';
    return 0;
}

而用单调队列，我们就可以用$O(n-m)$的时间复杂度完成这道题。

单调队列，其中心思想就是在队列里保存可能成为区间极值的元素。

对于每一个新元素，都会经历一下过程：

1. 如果队头元素超出作用域了，就把它pop掉；

2. 如果队尾元素的优先级小于当前元素，就把它pop掉，否则来到第4步；

3. 回到第3步；

4. 把当前元素从队尾push进来吧！

5. 如果现在可以产生答案了，就输出一下吧！

由此便可以实现单调队列。

---

Show一下代码：

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int n, k, r[1000006];
deque<int> d;
int main()
{
    cin >> n >> k;
    for (int i{1}; i <= n; i++)
        cin >> r[i];
    for (int i{1}; i <= n; i++)
    {
        if (!d.empty() && i - d.front() >= k)
            d.pop_front();
        while (!d.empty() && r[d.back()] > r[i])
            d.pop_back();
        d.push_back(i);
        if (i >= k)
            cout << r[d.front()] << ' ';
    }
    d.clear();
    cout << endl;
    for (int i{1}; i <= n; i++)
    {
        if (!d.empty() && i - d.front() >= k)
            d.pop_front();
        while (!d.empty() && r[d.back()] < r[i])
            d.pop_back();
        d.push_back(i);
        if (i >= k)
            cout << r[d.front()] << ' ';
    }
    return 0;
}

---

最后，谢谢大家的观看！