【洛谷】P1886滑动窗口/【模板】单调队列，经典！

目录

题目

AC代码

详解

deque语法

---

一道经典的单调队列模板题 ！ ！ 

“如果一个选手比你小还比你强，你就可以退役了。” ——单调队列的原理

——算法学习笔记(66): 单调队列 - 知乎

题目

P1886 滑动窗口 /【模板】单调队列 - 洛谷

【普及/提高-】

AC代码 #include <bits/stdc++.h> using namespace std; int n, m; struct Node { int id;//编号 int val;//大小 }; deque<Node> q1;//min,队头最小&&在滑动窗口内 deque<Node> q2;//max vector<vector<int>> ans(2);//存答案 /* 1.使用deque维护单调队列需要注意： ①保证队头的极值性 ②保证范围的有效性，队头位于滑动窗口内 2.此单调队列：①时间单调性，②数值单调性 */ int main() { cin >> n >> m; Node node; for (int i = 1; i <= n; i++) { node.id = i; cin >> node.val; //q1,q2现有是否弹出 //队尾判断 while (!q1.empty() && node.val <= q1.back().val) q1.pop_back(); while (!q2.empty() && node.val >= q2.back().val) q2.pop_back(); //node.val进栈 //队尾进 q1.push_back(node); q2.push_back(node); //判断队头是否失效，即是否在滑动窗口内 while (i - q1.front().id >= m) q1.pop_front(); while (i - q2.front().id >= m) q2.pop_front(); //记录答案，i=m时第一个滑动窗口开始 if (i >= m) { ans[0].push_back(q1.front().val); ans[1].push_back(q2.front().val); } } //输出 //min for (int i = 0; i < ans[0].size(); i++) cout << ans[0][i] << " "; cout << endl; //max for (int i = 0; i < ans[1].size(); i++) cout << ans[1][i] << " "; return 0; }

详解 单调队列同时保证：1.时间是从旧到新的，即始终从队尾入队，进一步，便于判断元素是否在滑动窗口内，i - q1.front().id < m，2.如果队头是min，那么单调队列中的元素始终是从小到大的，即维护队头始终是最小值，反之同理 滑动窗口应用单调队列解题：1.窗口具有时效性，2.窗口内的元素始终动态变化，3.需要求窗口内的特定值，故满足：时效性+特定值的题可以考虑用单调队列求解 单调队列的原理：以最小单调队列为例，①元素值x和队尾比较，队尾所有大于x的值从队尾出，x从队尾进，②队头始终维护为最小值，③一般使用双向队列deque实现 注意：while (!q1.empty() && node.val <= q1.back().val) q1.pop_back();while (!q2.empty() && node.val >= q2.back().val) q2.pop_back();为了保证时间最新，所以判断时加上=，即越新越大（小），优先级越高

deque语法

插入元素：

在队列的末尾插入：使用 push_back()在队列的前端插入：使用 push_front()

删除元素：

从队列的末尾删除：使用 pop_back() 从队列的前端删除：使用 pop_front()

访问：

d[i]back()：返回队尾元素front()：返回队头元素