《算法竞赛从入门到国奖》算法基础:数据结构-单调队列
💡Yupureki:个人主页
✨个人专栏:《C++》 《算法》《Linux系统编程》《高并发内存池》
🌸Yupureki🌸的简介:
目录
前言
1. 【模板】单调队列 / 滑动窗口
算法原理
代码实现
2. 质量检测
算法原理
代码实现
前言
单调队列，顾名思义，就是存储的元素要么单调递增要么单调递减的队列。注意，这里的队列和普通的队列不一样，是一个双端队列，因此在数据结构上，我们一般选择deque
单调队列⼀般用于解决滑动窗口内最大值最小值问题，以及优化动态规划
1. 【模板】单调队列 / 滑动窗口
题目链接:
P1886 【模板】单调队列 / 滑动窗口 - 洛谷
算法原理
窗口内最大值：
从左往右遍历元素，维护一个单调递减的队列：
当前元素进队之后，注意维护队列内的元素在大小为k的窗口内；
此时队头元素就是最大值。
窗口内最小值：
从左往右遍历元素，维护一个单调递增的队列：
当前元素进队之后，注意维护队列内的元素在大小为k的窗口内；
此时队头元素就是最小值。
注意:
单调队列中一般用于滑动窗口求最大值或最小值，那么当滑动窗口移动时，还要移除不在窗口中的元素，具体实现方案:在队列中存储数组元素的下标，当新元素从队尾入队列后，他就是新的队尾，也是最新的元素，如果队尾元素的下标 - 队首元素的下标 >= 滑动窗口大小，则直接让队首出列
while (q.back() - q.front() >= k) q.pop_front();代码实现
#include <iostream> #include <vector> #include <deque> using namespace std; int main() { int n,k; cin >> n >> k; vector<int> v; deque<int> q; for (int i = 0; i < n; i++) { int num; cin >> num; v.push_back(num); } for (int i = 0; i < n; i++) { while (q.size() && v[q.back()] > v[i]) q.pop_back(); q.push_back(i); while (q.size() && q.back() - q.front() >= k) q.pop_front(); if(i >= k -1 && i < n) cout << v[q.front()] << " "; } while (q.size()) q.pop_front(); cout << endl; for (int i = 0; i < n; i++) { while (q.size() && v[q.back()] < v[i]) q.pop_back(); q.push_back(i); while (q.size() && q.back() - q.front() >= k) q.pop_front(); if (i >= k -1 && i < n) cout << v[q.front()] << " "; } return 0; }2. 质量检测
题目链接:
P2251 质量检测 - 洛谷
算法原理
滑动窗口求最小值，用递减的单调队列
代码实现
#include <iostream> #include <vector> #include <deque> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> v; for (int i = 0; i < n; i++) { int num; cin >> num; v.push_back(num); } deque<int> q; for (int i = 0; i < n; i++) { while (q.size() && v[q.back()] > v[i]) q.pop_back(); q.push_back(i); while (q.back() - q.front() >= m) q.pop_front(); if (i >= m-1) cout << v[q.front()]<<endl; } return 0; }