Description：

给定 $n,k$ 和一个长度为 $n$ 的序列，求最长的最大值最小值相差不超过 $k$ 的序列。

$1\leqslant n\leqslant 3\times 10^6$

Solution：

单调队列 $+$ 双指针，两个单调队列一个维护最大一个维护最小，如果差值过大，那么就弹掉下标小的队头，因为队头是区间最值，所以只有弹掉队头才能使答案减小，由于要区间最长，所以弹掉队头之后 $l$ 的值是原队头 $+1$ ，然后更新答案就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<deque>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int m,n;

#define MAXN 3000010

int a[MAXN];

int main()

{

	scanf("%d%d",&m,&n);

	for(int i = 1;i <= n;++i)a[i] = read();

	deque<int> qmax,qmin;

	int ans = 0;

	for(int r = 1,l = 1;r <= n;++r)

	{

		while(!qmax.empty() && a[qmax.back()] <= a[r])qmax.pop_back();qmax.push_back(r);

		while(!qmin.empty() && a[qmin.back()] >= a[r])qmin.pop_back();qmin.push_back(r);

		while(a[qmax.front()] - a[qmin.front()] > m)

		{

			if(qmax.front() < qmin.front())l = qmax.front() + 1,qmax.pop_front();

			else l = qmin.front() + 1,qmin.pop_front();

		}

		ans = max(ans,r - l + 1);

	}

	cout << ans << endl;

	return 0;

}