154. 滑动窗口

注意q[N]数组记录的是a[N]数组的下标。
主要的思想和单调栈类似。

#include<iostream>
#include<queue>
using namespace std;
const int N=1000010;
int q[N],a[N];

int main(){
    int n,k,x;
    int hh=0,tt=-1;
    scanf("%d%d",&n,&k);
    
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    
    for(int i=0;i<n;i++){
        if(hh<=tt && i-k+1>q[hh])hh++;
        while(hh<=tt && a[q[tt]]>=a[i])tt--;
        q[++tt]=i;
        if(i>=k-1)printf("%d ",a[q[hh]]);
    }
    
    puts("");
    hh=0,tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt && i-k+1>q[hh])hh++;
        while(hh<=tt && a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i>=k-1)printf("%d ",a[q[hh]]);
    }
    
    return 0;
}

使用deque代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int arr[N],n,k;
deque<int>q,q2;

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>arr[i];
    
    for(int i=0;i<n;i++){
        if(q.size() && q.front()<i-k+1)q.pop_front();
        while(q.size() && arr[q.back()]>=arr[i])q.pop_back();
        q.push_back(i);
        if(i>=k-1)cout<<arr[q.front()]<<" ";
    }
    cout<<endl;
    q=q2;
    for(int i=0;i<n;i++){
        if(q.size() && q.front()<i-k+1)q.pop_front();
        while(q.size() && arr[q.back()]<=arr[i])q.pop_back();
        q.push_back(i);
        if(i>=k-1)cout<<arr[q.front()]<<" ";
    }
    
    return 0;
}