#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