题意：求在一段序列中满足m<=max-min<=k的最大长度。
解题关键：单调队列+dp，维护前缀序列的最大最小值，一旦大于k，则移动左端点，取max即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<iostream> 6 #include<cmath> 7 #define maxn 1000005 8 using namespace std; 9 typedef long long ll; 10 int n,m,k; 11 int qmin[maxn],qmax[maxn],a[maxn]; 12 int main(){ 13 while(scanf("%d%d%d",&n,&m,&k)!=EOF){ 14 for(int i=1;i<=n;i++) scanf("%d",a+i); 15 int head1=0,rear1=0,head2=0,rear2=0,now=1,ans=0; 16 for(int i=1;i<=n;i++){ 17 while(head1<rear1&&a[qmin[rear1-1]]>a[i]) rear1--; 18 while(head2<rear2&&a[qmax[rear2-1]]<a[i]) rear2--; 19 qmin[rear1++]=i; 20 qmax[rear2++]=i; 21 while(head1<rear1&&head2<rear2&&a[qmax[head2]]-a[qmin[head1]]>k){ 22 if(qmin[head1]<qmax[head2]) now=qmin[head1++]+1; 23 else now=qmax[head2++]+1; 24 } 25 if(head1<rear1&&head2<rear2&&a[qmax[head2]]-a[qmin[head1]]>=m){ 26 ans=max(ans,i-now+1); 27 } 28 } 29 printf("%d ",ans); 30 } 31 }