题目大意：

给定一个序列，求出一个最长的序列 $(i,j)$ ，使得其中最大值与最小值的差不超过 $k$ 。

前置知识：

1.单调队列 。

思路：

这道题是一个区间问题，可以采用枚举左端点，快速查找右端点的思路。

由于 $n \le 3000000$ ，所以，我们可以猜测，这道题是 $O(n)$ 的做法。

那么 $O(n)$ ，枚举左端点，$O(1)$ 查找右端点，最常用的方法，是什么呢？

就是单调队列！

根据这道题的规定，不管有没有用，可以 $O(1)$ 处理出每个点右边的上升序列和下降序列。

考虑如何处理出右端点。

不能盲目查找，这时候，又一个区间常用策略来了，单调性。

对于一个以 $i$ 为左端点，$j$ 为满足规定的最长的以 $i$ 为左端点的序列，那么对于 $(i+1)$ ，左端点不需要 $< j$ ，

因为 $i$ 都已经不满足规定了，而集合的增大不会减小最大值，增大最小值，从而最大值与最小值的差永远 $>k$ 。

假设上升序列的对首为 $s1$ ，下降序列为 $s_2$ ，假如 $a_{s_2}-a_{s_1}>k$ ，是移动 $s_1$ ，还是移动 $s_2$ 呢 ?

想到规定当中的最长序列，那么假设 $s_2$ 的位置 $>$ $s_1$ 的位置，那么肯定是移动 $s_2$ 最优，反之，同理。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int kMax=3e6+5;
const int kInf=1e9;

int k,n;
int a[kMax];
int ans;

int s1[kMax],s2[kMax],t1,t2,h1=1,h2=1;//s1递减,s2递增

int main(){
	scanf("%d%d",&k,&n);
	for(int i=1;i<=n;++i){scanf("%d",&a[i]);}
	for(int i=1;i<=n;++i){
		bool flag=1;
		while(t1>=h1&&a[s1[t1]]<=a[i]){t1--;}	
		s1[++t1]=i;
		while(t2>=h2&&a[s2[t2]]>=a[i]){t2--;}
		s2[++t2]=i;
		while(a[s1[h1]]-a[s2[h2]]>k){
			if(h1<t1&&s1[h1]<s2[h2]){h1++;}
			else if(h2<t2){h2++;}
			else{flag=0;break;}
		}
		if(flag){ans=max(ans,i-max(s1[h1-1],s2[h2-1]));}
	}
	printf("%d\n",ans);
	return 0;
}