维护两个单调队列,一个存储当前点之前的最大值。
另外一个存储当前点之前的最小值。
若最大值与最小值之间的差大于k,那么就把最大值和最小值中位置靠前的往后移。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<queue> using namespace std; //#define INF ((1<<30)-1) #define INF 0xfffff #define maxn 220000 #define LL long long #define MOD 1000000009 struct list { int val; int x; }p[maxn],q[maxn],pp; int main() { int n,m,k,i,x; while(~scanf("%d%d%d",&n,&m,&k)) { int h1,h2,t1,t2; h1=h2=1; t1=t2=0; int last1,last2,ans; ans=last1=last2=0; for(i=1;i<=n;i++) { scanf("%d",&x); pp.x=i; pp.val=x; while(t1>=h1&&p[t1].val<x)t1--; p[++t1]=pp; while(t2>=h2&&q[t2].val>x)t2--; q[++t2]=pp; while(p[h1].val-q[h2].val>k) { if(p[h1].x<q[h2].x) { last1=p[h1++].x; } else last2=q[h2++].x; } if(p[h1].val-q[h2].val>=m) { ans=max(ans,i-max(last1,last2)); } } cout<<ans<<endl; } return 0; }
hud-3530-Subsequence-维护两个单调队列,布布扣,bubuko.com
原文:http://blog.csdn.net/rowanhaoa/article/details/24935863