单调队列(最大 最小)

2021/5/11 10:25:46

本文主要是介绍单调队列(最大 最小),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int a[maxn],q[maxn],hh,tt=-1;
int main()
{
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i-k+1>q[hh])hh++;
        while(hh<=tt&&a[i]<=a[q[tt]])tt--;
        q[++tt]=i;
        if(i+1>=k)cout<<a[q[hh]]<<" ";
    }
    cout<<"\n";
    hh=0,tt=-1;
    for(int i=0;i<n;i++){
        if(i-k+1>q[hh])hh++;
        while(hh<=tt&&a[i]>=a[q[tt]])tt--;
        q[++tt]=i;
        if(i+1>=k)cout<<a[q[hh]]<<" ";
    }
    return 0;
}

  



这篇关于单调队列(最大 最小)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程