每日一题

滑动窗口
板子

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000010;
int a[N];
int q[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int hh=0,tt=-1;
    vector<int>res;
    hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(i-q[hh]>=k)   hh++;
        while(hh<=tt  &&   a[i]<=a[q[tt]])   tt--;
        q[++tt]=i;
        if(i>=k)
            res.push_back(a[q[hh]]);
    }
    for(auto x:res)
        cout<<x<<" ";
    cout<<endl;
    res.clear();
    hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(i-q[hh]>=k)   hh++;
        while(hh<=tt  &&   a[i]>=a[q[tt]])   tt--;
        q[++tt]=i;
        if(i>=k)
            res.push_back(a[q[hh]]);
    }
    for(auto x:res)
        cout<<x<<" ";
    cout<<endl;
    res.clear();

   return 0;
}