存一下单调队列板子

题意

一个长度为n的序列，求每k个连续的元素的最大值和最小值。

解题思路

用两遍单调队列分别维护最大值和最小值。

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int a[1000010],que[1000010];  //单调队列中存数组下标
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=1,r=1;
    que[r++]=1;
    if(k==1) cout<<a[1]<<" ";
    //维护最小值
    for(int i=2;i<=n;i++){
        //若队列非空，且队首已不再窗口内，队首出队
        if(l<r&&i-que[l]>=k) l++;
        //若队列非空，且队尾所指元素大于当前元素，由于要维护最小值，队尾出队
        while(l<r&&a[i]<a[que[r-1]]) r--;
        que[r++]=i;
        if(i>=k) cout<<a[que[l]]<<" ";
    }
    cout<<endl;
    //维护最大值
    l=r=1;
    que[r++]=1;
    if(k==1) cout<<a[1]<<" ";
    for(int i=2;i<=n;i++){
        //若队列非空，且队首已不再窗口内，队首出队
        if(l<r&&i-que[l]>=k) l++;
        //若队列非空，且队尾所指元素小于当前元素，由于要维护最大值，队尾出队
        while(l<r&&a[i]>a[que[r-1]]) r--;
        que[r++]=i;
        if(i>=k) cout<<a[que[l]]<<" ";
    }
    cout<<endl;
    return 0;
}