【每日一题】滑动窗口题解

Solution

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6 + 5;
const ll mod = 1e9 + 7;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int n, m;
int q[N], a[N];
vector<int> v;
void solve1(){
  int h = 1, t = 0; // h是队头 t是队尾
  for(int i = 1; i <= n; i++){
    while(h <= t && q[h] + m <= i) h++; // 当队首元素已超出滑动窗口 从队头出队
    while(h <= t && a[i] < a[q[t]]) t--; // 这里是a[i] < a[q[t]] 比a[i]都大的都从队尾出队;
    q[++t] = i;
    if(i >= m) cout << a[q[h]] << ' ';
  }
  cout << "\n";
}
void solve2(){ // 求最大值
  int h = 1, t = 0; // h是队头 t是队尾
  for(int i = 1; i <= n; i++){
    while(h <= t && q[h] + m <= i) h++; // 当队首元素已超出滑动窗口 从队头出队
    while(h <= t && a[i] > a[q[t]]) t--; //这里是 a[i] > a[q[t]] 比a[i]都小的都从队尾出队;
    q[++t] = i;
    if(i >= m) cout << a[q[h]] << ' ';
  }
  cout << "\n";
}
int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  solve1(); // 求最小值
  solve2(); // 求最大值
  return 0;
}