#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int a[N];
int ans_min[N];
int ans_max[N];
int main(){
int n,m,c;
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
deque<int> q1,q2;
for(int i=1;i<=n;i++){
while(q1.size()>0&&a[q1.back()]>=a[i])q1.pop_back();
q1.push_back(i);
if(q1.front()==i-m)q1.pop_front();
while(q2.size()>0&&a[q2.back()]<=a[i])q2.pop_back();
q2.push_back(i);
if(q2.front()==i-m)q2.pop_front();
if(i>=m){
ans_min[i]=a[q1.front()];
ans_max[i]=a[q2.front()];
}
}
int flag=0;
for(int i=m;i<=n;i++){
if(ans_max[i]-ans_min[i]<=c){
printf("%d%c",i-m+1," \n"[i==n]);
flag=1;
}
}
if(!flag)puts("NONE");
return 0;
}
一道单调队列的例题
题目链接 poj2823