滑动窗口（单调队列维护窗口）-acwing

题目：

154. 滑动窗口 - AcWing题库

代码（删除队列窗口多余的=>单调队列）

判断最值是否滑出窗口可以放在 入队的后面。

但是，判断，准备入队元素比前面小，要从队尾出队，放在入队前。

总之，是否滑出窗口在最值输出前操作完就行。

单调队列是用来维护当前窗口的（主要是多余的删去了）

1. 多余值队尾出队（因为要将当前最小的输出出去，前面更大的都要队尾出去）
2. 入队
3. 将滑出窗口的索引队头出队
4. 输出队头索引的值

从最小值输出开始做：

队列维护窗口的最小值的索引。每次滑动窗口，输出队头索引的数组a值。

#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int n, k;
int q[N], a[N];int main() {cin >> n >> k;for(int i = 0; i < n; i ++) cin >> a[i];int hh = 0, tt = -1;for(int i = 0; i < n; i ++) {if(hh<=tt && q[hh]<i-k+1) hh ++; // 滑出去了while(hh<=tt && a[q[tt]]>=a[i]) tt--; //前面的大于后面的，去掉前面的q[++tt] = i; //索引入队if(i>=k-1) cout << a[q[hh]] << " "; // 从遍历完第一个窗口开始输出栈顶}puts("");hh = 0, tt = -1;for(int i = 0; i < n; i ++) {if(hh<=tt && q[hh]<i-k+1) hh ++;while(hh<=tt && a[q[tt]]<=a[i]) tt --;q[++tt] = i;if(i>=k-1) cout << a[q[hh]] << " ";}puts("");return 0;
}

 代码（使用deque双端队列存窗口最值）

#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int a[N];
int main() {int n, k;cin >> n >> k;for(int i = 0; i < n; i ++) cin >> a[i];deque<int> q;for(int i = 0; i < n; i ++) {while(q.size() && q.back() > a[i]) q.pop_back();q.push_back(a[i]);//窗口滑动最小值出去了if(i>=k && q.front() == a[i-k]) q.pop_front();if(i>=k-1) cout << q.front() << " ";}puts("");q.clear();for(int i = 0; i < n; i ++) {while(q.size() && q.back() < a[i]) q.pop_back();q.push_back(a[i]);if(i>=k-1 && q.front() == a[i-k]) q.pop_front();if(i>=k-1) cout << q.front() << " ";}puts("");return 0;
}