用数组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; }