NO.77十六届蓝桥杯备战|数据结构-单调队列|质量检测(C++)

1. 什么是单调队列？
   单调队列，顾名思义，就是存储的元素要么单调递增要么单调递减的队列。注意，这⾥的队列和普通的队列不⼀样，是⼀个双端队列。
2. 单调队列解决的问题
   ⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题，以及优化动态规划

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

窗⼝内最⼤值：
从左往右遍历元素，维护⼀个单调递减的队列：

• 当前元素进队之后，注意维护队列内的元素在⼤⼩为k的窗⼝内；
• 此时队头元素就是最⼤值。
  窗⼝内最⼩值：
  从左往右遍历元素，维护⼀个单调递增的队列：
• 当前元素进队之后，注意维护队列内的元素在⼤⼩为k的窗⼝内；
• 此时队头元素就是最⼩值

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;int n, k;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];deque<int> q; //存下标//最小值，递增队列for (int i = 1; i <= n; i++){while (q.size() && a[q.back()] >= a[i]) q.pop_back();q.push_back(i);//判断队列元素是否合法if (q.back() - q.front() + 1 > k) q.pop_front();if (i >= k) cout << a[q.front()] << " ";}cout << endl;//最大值，递减队列q.clear();for (int i = 1; i <= n; i++){while (q.size() && a[q.back()] <= a[i]) q.pop_back();q.push_back(i);//判断队列元素是否合法if (q.back() - q.front() + 1 > k) q.pop_front();if (i >= k) cout << a[q.front()] << " ";}cout << endl;return 0;
}

P2251 质量检测 - 洛谷

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;int n, m;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;deque<int> q;for (int i = 1; i <= n; i++) {cin >> a[i];while (q.size() && a[q.back()] >= a[i]) q.pop_back();q.push_back(i);if (q.back() - q.front() + 1 > m) q.pop_front();if (i >= m) cout << a[q.front()] << endl;}return 0;
}