滑动窗口最大值
滑动窗口极值问题

如果使用枚举，那么枚举次数近似等于 窗口大小×总数组数量，显然暴力求解太过复杂
注意到窗口滑动，最前位进入，最后位退出，中间量不变，可以记下窗口内元素，只需要删除推出值、增加进入值
尽管如此，窗口内的元素乱序使得仍旧需要遍历，为方便排序
因为是两端出入，使用采用deque

单调队列存的不只是当前窗口的最值，而是可能成为后续窗口最值的候选下标集合。只保留最值则失去下一个窗口判断最小值的候选，结果会错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,k;cin>>n>>k;
 vector<int>a(n);
 deque<int>maxn;
 deque<int>minn;
 vector<int>max1;
 vector<int>min1;
 for(int i=0;i<n;i++)cin>>a[i];
 for(int i=0;i<n;i++){
  while(!maxn.empty()&&maxn.front()<i-k+1){ //弹出窗口范围外的索引
   maxn.pop_front();
  }
  while(!minn.empty()&&minn.front()<i-k+1){ //同上
   minn.pop_front();
  }
  while(!minn.empty()&&a[minn.back()]>=a[i]){  //维护单调递增队列，队头最小
   minn.pop_back();
  }
  minn.push_back(i);
  while(!maxn.empty()&&a[maxn.back()]<=a[i]){  //维护单调递减队列，队头最大
   maxn.pop_back();
  }
  maxn.push_back(i);
  if(i>=k-1){
   max1.push_back(a[maxn.front()]); //记录保存窗口内极值
   min1.push_back(a[minn.front()]);
  }
 }
 for(int i=0;i<min1.size();i++)cout<<min1[i]<< " ";
 cout<<"\n";
 for(int i=0;i<max1.size();i++)cout<<max1[i]<< " ";
 return 0;
}