Acwing 154. 滑动窗口

滑动窗口

输入:

8 3
1 3 -1 -3 5 3 6 7

输出：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路：

使用双端队列（deque）来维护一个区间的最值

具体做法：

  双端队列里面存储元素的下标，我们先考虑如何维护区间里的数：一、保证队列里的下标是升序的，这样有利于维护在区间里的数。：当枚举到第i个元素时，维护队首值大于等于i - k + 1二、如何保证最值？1、最小值：当枚举到第i个元素时，我们从队尾开始往前判断，删除所有大于等于a[i]的下标，这样我们就保证剩下的都是小于a[i]的（即队首肯定是最小的）。最大值 ：当枚举到第i个元素时，我们从队尾开始往前判断，删除所有小于等于a[i]的下标，这样我们就保证剩下的都是大于a[i]的（即队首肯定是最大的）。

数组维护单调队列代码：

#include<iostream>
#include<stack>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<deque>using namespace std;
const int maxn = 1e6 + 10;int a[maxn];int q[maxn]; // 单调队列int main(){int n, k;cin >> n >> k;for(int i = 1; i <= n; i ++ ) cin >> a[i];int h = 1, t = 0; // 队首 h = 1, 队尾初始为 0, 入队为 q[++t] = xfor(int i = 1; i <= n; i ++ ){ // 维护区间最小值while(h <= t && a[q[t]] >= a[i]) t --; // 将前面大于等于 a[i]的都删除 q[ ++ t] = i; // 将第 i 下标入队if(q[h] < i - k + 1) h ++; // 判断队头的下标是否越界if(i >= k) cout << a[q[h]] << " "; // 如果区间长度够了，就开始输出 每个区间最小值}cout << endl;h = 1, t = 0; // 初始化单调队列for(int i = 1; i <= n; i ++ ){ // 维护最大值while(h <= t && a[q[t]] <= a[i]) t --; //将前面小于等于 a[i]的都删除q[ ++ t] = i; //  将第 i 下标入队if(q[h] < i - k + 1) h ++;// 判断队头的下标是否越界if(i >= k) cout << a[q[h]] << " ";// 如果区间长度够了，就开始输出 每个区间最大值}return 0;
}

STL单调队列代码：

#include<iostream>
#include<stack>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<deque>using namespace std;
const int maxn = 1e6 + 10;int a[maxn];// int q[maxn];
deque<int> q;int main(){int n, k;cin >> n >> k;for(int i = 1; i <= n; i ++ ) cin >> a[i];for(int i = 1; i <= n; i ++ ){while(q.size() && a[q.back()] >= a[i]) q.pop_back();q.push_back(i);if(q.front() < i - k + 1) 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.front() < i - k + 1) q.pop_front();if(i >= k) cout << a[q.front()] << " ";}return 0;
}