滑动窗口（单调栈）

思路：单调栈

#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
const int MAX =1e6+5;
const int mod=998244353;
struct node
{
    int v,pos;
}q[MAX];
int a[MAX];

int main(){
 SIS;
  int n,k;
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
      cin>>a[i];
  }
  int h=1,t=0;
  for(int i=1;i<=n;i++)//递减
  {
      while(h<=t&&q[h].pos+k<=i)++h;
      while(h<=t&&q[t].v>=a[i])--t;
      q[++t].v=a[i];q[t].pos=i;
      if(i>=k)cout<<q[h].v<<' ';
  }
  cout<<endl;
  h=1,t=0;
  for(int i=1;i<=n;i++)//递增
  {
      while(h<=t&&q[h].pos+k<=i)++h;
      while(h<=t&&q[t].v<=a[i])--t;
      q[++t].v=a[i];q[t].pos=i;
      if(i>=k)cout<<q[h].v<<' ';
  }

    return 0;
}