数据结构

单调队列

P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=5010;
const int MAXN=1e6+10;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll a[MAXN],b[MAXN];
std::deque<ll> dqmax;
std::deque<ll> dqmin;
//时间复杂度为O(n)
void solve()
{
    int n,k;    std::cin>>n>>k;
    for(int i=1;i<=n;i++)   std::cin>>a[i];

    //求区间的最小值 维护的是一个单调递增序列
    for(int i=1;i<=n;i++)
    {
        //超过滑动窗口的长度 直接弹出头部
        if(!dqmin.empty() && i-dqmin.front()>=k)    dqmin.pop_front();
        //维护单调递增序列
        while(!dqmin.empty() && a[dqmin.back()]>a[i])   dqmin.pop_back();
        //都满足 则插入i 注意插入的是编号
        dqmin.push_back(i);
        //i超出k 开始输出
        if(i>=k)      std::cout<<a[dqmin.front()]<<" ";
    }
    std::cout<<"\n";

    //求区间的最大值 维护的是一个单调递增的序列
    for(int i=1;i<=n;i++)
    {
        //超过滑动窗口的长度 直接弹出头部
        if(!dqmax.empty() && i-dqmax.front()>=k)    dqmax.pop_front();
        //维护单调递增序列
        while(!dqmax.empty() && a[dqmax.back()]<a[i])   dqmax.pop_back();
        //都满足 则插入
        dqmax.push_back(i);
        //i超出k 开始输出
        if(i>=k)      std::cout<<a[dqmax.front()]<<" ";
    }
}
int main(){
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}