题解 | #Sliding Window#

用数组du作为单调队列，把对应a中的下标记录下来。l和r分别是数组du的左右界。以求区间最大为例，如果后来的元素更大，则前面比它小的元素就没机会成为最大了，直接去掉。若后来的元素更小，由于位序偏后，可能会成为某个区间的最大。当区间里的数多于k个，就把最前面的元素去掉。最终du对应a中的元素单调下降，最前面的元素a[du[l]]就是最大。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll a[1000010];
int du[1000010];//记录区间的第i个数在a中的下标 
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i=0;i<n;i++)
        cin >> a[i];
    int l=0;
    int r=1;//左闭右开的区间
    //du是单调队列，存放在a中的下标 
    du[0]=0;//最开始的元素下标为0 
    if(k==1)    cout << a[0] << " ";//保证a的首元素会被输出
    for(int i=1;i<n;i++){//遍历a中元素 
        if(i-du[l]>=k)    l++;
        while(a[du[r-1]]>=a[i] && r>l)    r--;//注意左闭右开，du最后一位是r-1 
        du[r++]=i;
        if(i>=k-1)    cout << a[du[l]] << " ";
    } 
    cout << "\n";

    l=0;
    r=1;//左闭右开的区间
    //du是单调队列，存放在a中的下标 
    du[0]=0;//最开始的元素下标为0 
    if(k==1)    cout << a[0] << " ";
    for(int i=1;i<n;i++){//遍历a中元素 
        if(i-du[l]>=k)    l++;
        while(a[du[r-1]]<=a[i] && r>l)    r--;
        du[r++]=i;

        if(i>=k-1)    cout << a[du[l]] << " ";
    } 
    cout << "\n";
    return 0;
}