题目分析

利用单调栈思想

相关代码实现

#include<bits/stdc++.h>
using namespace std;

int A[1000010];
int MAX[1000010];
int MIN[1000010];

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>A[i];
    }

    int hh=0;
    int tt=-1;
    for(int i=0;i<n;i++){
        while(hh<=tt&&MIN[hh]<i-k+1) hh++; //MIN[hh]-MIN[tt]中存储的是A[i-k+1]-A[i]范围内的单调增序元素的位置

        while(hh<=tt&&A[MIN[tt]]>=A[i]) tt--; //保证算上A[i]后仍然是增序

        MIN[++tt]=i;

        if(i>=k-1) cout<<A[MIN[hh]]<<" ";
    }
    cout<<endl;

    hh=0;tt=-1;
    for(int i=0;i<n;i++){
        while(hh<=tt&&MAX[hh]<i-k+1) hh++; //MAX[hh]-MAX[tt]中存储的是A[i-k+1]-A[i]范围内的单调降序元素的位置

        while(hh<=tt&&A[MAX[tt]]<=A[i]) tt--;  //保证算上A[i]后仍然是降序

        MAX[++tt]=i;

        if(i>=k-1) cout<<A[MAX[hh]]<<" ";
    }
    cout<<endl;

    return 0;
}