单调队列
1.什么是单调队列？
2.单调队列解决的问题
2.1【模板】单调队列
题目描述
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。
例如，对于序列 [1,3,−1,−3,5,3,6,7] 以及 k=3，有如下过程：
窗口位置[1 3 -1] -3 5 3 6 7 1 [3 -1 -3] 5 3 6 7 1 3 [-1 -3 5] 3 6 7 1 3 -1 [-3 5 3] 6 7 1 3 -1 -3 [5 3 6] 7 1 3 -1 -3 5 [3 6 7]最小值−1−3−3−333最大值335567
输入格式
输入一共有两行，第一行有两个正整数 n,k；
第二行有 n 个整数，表示序列 a。
输出格式
输出共两行，第一行为每次窗口滑动的最小值；
第二行为每次窗口滑动的最大值。
输入输出样例
输入 #1复制
8 3 1 3 -1 -3 5 3 6 7
输出 #1复制
-1 -3 -3 -3 3 3 3 3 5 5 6 7
说明/提示
【数据范围】
对于 50% 的数据，1≤n≤105；
对于 100% 的数据，1≤k≤n≤106，ai∈[−231,231)。
【解法】
【参考代码】
#include <iostream> #include <deque> // 行2：导入双端队列（可以从队头/队尾删元素） using namespace std; const int N = 1e6 + 10; // 行4：序列最长100万+10个数字 int n, k; // 行5：n是序列长度，k是窗口大小 int a[N]; // 行6：存储序列的数字（a[1]是第一个，a[2]第二个...） int main() // 行7：程序入口 { cin >> n >> k; // 行9：读入n和k（比如8和3） for(int i = 1; i <= n; i++) cin >> a[i]; // 行10：读入序列，存到a[1]-a[8] deque<int> q; // 行12：双端队列，存的是数字的“下标”（不是数字本身） // 第一部分：算窗口最小值（维护单调递增队列） for(int i = 1; i <= n; i++) // 行15：遍历每个数字（从第1个到第8个） { // 行17：如果队列不为空，且队尾下标对应的数字 >= 当前数字 → 删掉队尾 while(q.size() && a[q.back()] >= a[i]) q.pop_back(); q.push_back(i); // 行18：把当前数字的下标加入队尾 // 行20：判断队列里的数字是否超出窗口范围（窗口长度不能超过k） if(q.back() - q.front() + 1 > k) q.pop_front(); // 行22：只有当i >= k时（窗口已经滑够3个数字），才输出队头的最小值 if(i >= k) cout << a[q.front()] << " "; } cout << endl; // 行24：最小值输出完，换行 // 第二部分：算窗口最大值（维护单调递减队列） q.clear(); // 行27：清空队列，重新用 for(int i = 1; i <= n; i++) // 行28：再次遍历每个数字 { // 行30：如果队列不为空，且队尾下标对应的数字 <= 当前数字 → 删掉队尾 while(q.size() && a[q.back()] <= a[i]) q.pop_back(); q.push_back(i); // 行31：把当前数字的下标加入队尾 // 行33：判断是否超出窗口范围，超出则删队头 if(q.back() - q.front() + 1 > k) q.pop_front(); // 行35：i >= k时，输出队头的最大值 if(i >= k) cout << a[q.front()] << " "; } cout << endl; // 行37：最大值输出完，换行 return 0; // 行38：程序结束 }2.2质量检测
题目描述
为了检测生产流水线上总共 N 件产品的质量，我们首先给每一件产品打一个分数 A 表示其品质，然后统计前 M 件产品中质量最差的产品的分值 Qm=min{A1,A2,⋯,Am}，以及第 2 至第 M+1 件的 Qm+1，Qm+2…… 最后统计第 N−M+1 至第 N 件的 Qn。根据 Q 再做进一步评估。
请你尽快求出 Q 序列。
输入格式
输入共两行。
第一行共两个数 N、M，由空格隔开。含义如前述。
第二行共 N 个数，表示 N 件产品的质量。
输出格式
输出共 N−M+1 行。
第 1 至 N−M+1 行每行一个数，第 i 行的数 Qi+M−1。含义如前述。
输入输出样例
输入 #1复制
10 4 16 5 6 9 5 13 14 20 8 12
输出 #1复制
5 5 5 5 5 8 8
说明/提示
[数据范围]
对于 30% 的数据，N≤1000。
对于 100% 的数据，M≤N≤105,Ai≤106。
【解法】
#include <iostream> #include <deque> using namespace std; const int N = 1e6 + 10; // 最多支持100万+10个产品 int n, k; // n是产品总数，k是窗口大小（对应题目里的M） int a[N]; // 存储每个产品的质量分（a[1]是第1个，a[2]是第2个...） int main() { cin >> n >> k; // 读入n=10，k=4 deque<int> q; // 双端队列，存的是“产品的下标”（不是分数本身） // 遍历每个产品（从第1个到第10个） for(int i = 1; i <= n; i++) { cin >> a[i]; // 读入当前产品的分数（比如i=1时读16，i=2时读5...） // 核心1：维护队列“从小到大”（单调递增），保证队头是最小值 // 如果队列不为空，且队尾下标对应的分数 ≥ 当前分数 → 删掉队尾 while(q.size() && a[q.back()] >= a[i]) q.pop_back(); q.push_back(i); // 把当前产品的下标加入队尾 // 核心2：保证队列里的下标都在窗口内（窗口长度不能超过k） // 当前下标 - 队头下标 +1 > k → 队头超出窗口，删掉 if(i - q.front() + 1 > k) q.pop_front(); // 核心3：窗口滑够k个产品后，输出队头对应的最小值（每行一个） if(i >= k) cout << a[q.front()] << endl; } return 0; }
