滑动窗口（数据结构）

佚名 4年前 (2020-04-12) 算法 598人围观抢沙发百度已收录

滑动窗口：有两个指针L,R。加入一个数R往右移动，减去一个数L往右移动。

一般需要维护窗口中的最大值或者最小值，询问复杂度可以可以O（1）。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

一般需要双向队列的辅助，例如题目：滑动窗口

假设是一个需要维护最大值的窗口，那么双向队列里的数组应该是“大->小”，

为了满足这个条件，后面加入数x时，需要把小于等于x的数都弹出，再去压入双向队列，

为什么等于的也要弹出，因为x的下标一定比弹出数的下打大，所以x失效时间比之前的迟，那不如

把相同的早过期的数弹出。

滑动窗口维护的时候一般需要考虑当前队列中的最大值或者最小值是否过期。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <deque>
 4 
 5 using namespace std;
 6 
 7 void solve(){
 8     
 9     int N, K;
10     cin >> N >> K;
11     deque<int > Min;
12     deque<int > Max;
13     vector<int > ans[2];
14     vector<int > arr(N);
15     for(auto& it : arr) cin >> it;
16     // for(auto x : arr) cout << x << " ";
17     // cout << endl;
18     //压入下标，可以通过下标去索引数组的值
19     for(int i = 0; i < N; ++i){
20         while(!Min.empty() && arr[Min.back()] >= arr[i]) Min.pop_back();
21         while(!Max.empty() && arr[Max.back()] <= arr[i]) Max.pop_back();
22         Min.push_back(i);
23         Max.push_back(i);
24         if(i >= K - 1){
25             while(!Min.empty() && Min.front() + K - 1 < i ) Min.pop_front(); //最小值过期了
26             while(!Max.empty() && Max.front() + K - 1 < i ) Max.pop_front(); //最大值过期了
27             if(Min.empty() || Max.empty()) cout << "error" << endl;
28             ans[0].push_back(arr[Max.front()]);
29             ans[1].push_back(arr[Min.front()]);
30         }
31     }
32     for(auto x : ans[1]) cout << x << " ";
33     cout << endl;
34     for(auto x : ans[0]) cout << x << " ";
35     cout << endl;
36 }
37 
38 int main(){
39     
40     ios::sync_with_stdio(false);
41     cin.tie(0);
42     cout.tie(0);
43     solve();
44     
45     return 0;
46 }