Loading... 顾名思义，单调队列是一个 "单调" 的 "队列"。 "单调" 指队列中的元素是递增（或递减）的。 此"队列"非普通队列，需要双端队列。良心的STL已经为我们准备好了队列`queue`类和双端队列`deque`类（见下文）。 求连续m个数中的最大值。当一个数进入所要 "寻找" 最大值的范围中时，如这个数比先入队的数更大，就淘汰掉（pop）先入队的数，将该数入队。 这相当于维护一个递减的队列，达到减少重复的比较次数的效果。由于维护的队列在查询范围内且递减，队头必是该查询区域内的最大值，因此输出队头即可。 *上文参考[单调队列 - Ol Wiki](https://oi-wiki.org/ds/monotonous-queue/)* ## 题解 [洛谷 P1440](https://www.luogu.com.cn/problem/P1440) ### 分析 显然，这是一道水得不能再水的模板题。暴力枚举的时间复杂度是$O(n^2)$，显然会超时。所以维护一个单调队列，时间复杂度是$O(n)$。 注意判断是否队空，如果为空则不要查看或pop了。 ### 代码 ```cpp #include <cstdio> #include <deque> using std::deque; int n, m, a[2000001]; deque<int> qu; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", a+i); } printf("0\n"); for(int i = 0; i < n-1; ++i) { while(!qu.empty() && i >= qu.front()+m) qu.pop_front(); while(!qu.empty() && a[i] <= a[qu.back()]) qu.pop_back(); qu.push_back(i); printf("%d\n", a[qu.front()]); } return 0; } ``` ## STL deque 常用成员函数表 | 操作 | 函数原型 | | - | - | | 尾部插入 | void push_back(); | | 头部插入 | void push_front(); | | 尾部删除 | void pop_back(); | | 头部删除 | void pop_front(); | | 查看尾部 | reference back() const; | | 查看头部 | reference front() const; | | 判断队空 | bool empty() const; | | 元素个数 | int size() const; | | 清空队列 | void clear(); | © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
