【每日一题】滑动窗口 (单调队列)

3月30日每日一题 : https://ac.nowcoder.com/discuss/394776

Solution

滑动窗口最值问题，就是单调队列的模板题。

先讲一下个人对单调队列的理解：
举个维护区间最小值的例子，
主要就是用 head 和 tail 双指针来对队列里的元素进行维护，
当 q[head]+m<=i 说明队首元素已经跟不上滑动窗口，所以移动 head 指针，
当 a[ q[tail] ]>a[i] 说明队尾元素比当前元素大，失去优先级，移动尾指针，
这样的话，那么 q[head] 就是窗口中最小元素的索引了。

for(int i=1;i<=n;i++){
    while(head<=tail&&q[head]+m<=i) ++head;
    while(head<=tail&&a[q[tail]]>a[i]) --tail;
    q[++tail]=i;
}

Code

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define ins insert
#define eps 1e-8
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const ull base=2333; const ull pp=19260811; const ull ppp=999998639;

const int manx=1e6+5;
const int mo=998244353;

ll q[manx],a[manx];

int main(){
    ll n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    ll head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[head]+k<=i) ++head;
        while(head<=tail&&a[q[tail]]>a[i]) --tail;
        q[++tail]=i;
        if(i>=k) printf("%lld ",a[q[head]]);
    }
    printf("\n");
    head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[head]+k<=i) ++head;
        while(head<=tail&&a[q[tail]]<a[i]) --tail;
        q[++tail]=i;
        if(i>=k) printf("%lld ",a[q[head]]);
    }
    return 0;
}