滑动窗口/单调队列

双端队列和单调队列

#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int a[N];
deque<int>q;                       //队列中的数据，实际上是元素在原序列中的位置
int main(){
  int n,m; scanf("%d%d",&n,&m);    //队列、窗口
  for(int i=1;i<=n;i++) scanf("%d",&a[i]); 
  for(int i=1;i<=n;i++){           //输出最小值 
  //队列反序     非空 并 队尾 > 入队元素
  while(!q.empty() && a[q.back()]>a[i]) q.pop_back();     //去尾 
    q.push_back(i);
    if(i>=m){                      //每个窗口输出一次，小于窗口宽度不输出
      /*   非空 并 队头 ≤ 窗口宽度  
             例： 队头    入队元素    窗口
     (元素索引)    5    ≤    8    -    3       */        
      while(!q.empty() && q.front()<=i-m) q.pop_front();  //删头 
      printf("%d ", a[q.front()]);
    }
  }
  printf("\n");
  while(!q.empty()) q.pop_front();  //清空，下面再用一次
  for(int i=1;i<=n;i++){            //输出最大值 
    //队列反序
    while(!q.empty() && a[q.back()]<a[i]) q.pop_back();   //去尾 
    q.push_back(i); 
    if(i>=m){
      while(!q.empty() && q.front()<=i-m) q.pop_front();  //删头 
      printf("%d ", a[q.front()]);
    }
  }
  printf("\n");
  return 0;
}

笔记：将滑动窗口里的元素放到队列里，队列里的元素按照正序或者倒序排列，如果队尾加入的元素影响元素排列就删尾。窗口滑动后数据也会更新，超出部分就删头，最后队首就是最大值或者最小值