NC50528

题意

给你一个长度为n的数组，依次求长度为k的区间中的最小值，最大值为多少。

思路

单调队列（双端队列） 时间复杂度 $O(N)$
单调队列性质：

队列中的元素其对应在原来的列表中的顺序必须是单调递增的。

队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以
求最小值的做法：维护一个单调队列，头部元素的下标为 $s$ ，尾部元素的后一位下标为 $t$ ，其中的值为 $x_i$ （存 $a$ 数组中的下标）使得 $[s,t)$ 中的元素满足 $x_i<x_{i+1}$ 且 $a_{x_i}<a_{x_{i+1}}$ 即下标递增下标所对应的值也是有序的(可自定义）。
最大值对应只是改变了对应值有序的排列方式。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int n,k,a[maxn],q[maxn],x[maxn],y[maxn];

void solve1(){
    int s=1,t=1;
    for(int i=1;i<=n;i++){
        while(s<t&&a[i]<=a[q[t-1]]) t--;//维护单调队列的单调性
        q[t++]=i;
        if(i>=k){
            x[i]=a[q[s]];
        }
        if(q[s]==i-k+1) s++;//不在滑动窗口范围内弹出
    }
}

void solve2(){
    int s=1,t=1;
    for(int i=1;i<=n;i++){
        while(s<t&&a[i]>=a[q[t-1]]) t--;
        q[t++]=i;
        if(i>=k){
            y[i]=a[q[s]];
        }
        if(q[s]==i-k+1) s++;
    }
}

void print(){
    for(int i=k;i<n;i++){
        cout<<x[i]<<" ";
    }
    cout<<x[n]<<'\n';
    for(int i=k;i<n;i++){
        cout<<y[i]<<" ";
    }
    cout<<y[n]<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    solve1();
    solve2();
    print();
    return 0;
}