【AcWing 154题解】滑动窗口

AcWing 154. 滑动窗口
【题目描述】

【输入输出样例】

在查看解析之前，先给自己一点时间思考哦！

【题解】
题目要求给定一个大小为n的数组，并且有一个大小为k的滑动窗口。窗口每次向右移动一个位置，要求计算窗口中的最大值和最小值。为了解决这个问题，我们可以使用双端队列的方式来优化滑动窗口的最大值和最小值查询。

双端队列的应用：利用双端队列来保持一个递减或递增的窗口。具体来说：
最大值：保持队列中元素的下标递减，从队列前面获取窗口的最大值。
最小值：保持队列中元素的下标递增，从队列前面获取窗口的最小值。

窗口的滑动：每次滑动窗口时，我们需要：
将新元素添加到队列，并维护队列中的元素顺序（递减或递增）。
移除已经不在当前窗口中的元素。
效率：每个元素最多进入队列一次，且最多被删除一次，因此时间复杂度为$O(n)$。
【参考代码】

#include <iostream>
using namespace std;const int N = 1e6 + 10;  // 定义最大数组长度
int a[N], q[N];  // a存储数组，q存储队列（用来存储窗口中元素的索引）
int n, k;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 && i - k + 1 > q[hh])hh++;// 维护递增队列，移除队列中所有比当前元素大的元素while(hh <= tt && a[q[tt]] >= a[i])tt--;// 将当前元素的下标加入队列q[++tt] = i;// 输出当前窗口的最小值if(i >= k - 1)cout << a[q[hh]] << " ";}cout << endl;// 计算每个窗口中的最大值hh = 0, tt = -1;  // 重置队列的头尾指针for(int i = 0; i < n; i++) {// 移除不在窗口中的元素if(hh <= tt && i - k + 1 > q[hh])hh++;// 维护递减队列，移除队列中所有比当前元素小的元素while(hh <= tt && a[q[tt]] <= a[i])tt--;// 将当前元素的下标加入队列q[++tt] = i;// 输出当前窗口的最大值if(i >= k - 1)cout << a[q[hh]] << " ";}cout << endl;return 0;
}