题目传送门
单调队列的题目还是滑动窗口最典型，如果猜到可以用单调队列解题，看看能否通过什么方法转化成滑动窗口（如二分答案）。单调队列的题一般涉及最大值和最小值的问题，好像有的题目也可以用ST表解决。
这道题因为知道是单调队列才做的（硬上单调队列...）
简化题意：找到(x)坐标相差最近的两个点，使它们的纵坐标差值大于等于(D)
（先将点按照(x)由小到大排序）
最开始两个思路：
思路一：枚举每个点，把它当做低的那个点（这样答案一定会被枚举到）。这就要找它左边比它高的点（右边的情况倒着再来一遍）。维护一个单调递减的序列，因为(x)使有序的，所以单调队列中越靠左的点里当前点越远，并且越高。因此二分出（或者直接枚举）一个符合条件的(y)，用它和当前点的距离更新答案。
思路二：二分一个答案(L)，还是枚举每个点，把它当做低的那个点（这样答案一定会被枚举到）。这就要找它左边比它高的点（右边的情况倒着再来一遍）。维护一个单调递减的序列，因为(x)使有序的，所以单调队列中越靠左的点里当前点越远，并且越高。所以二分出(x)据当前点小于等于(L)的单调队列中最左边的点，只要它们两个的纵坐标的差值大于等于(D)，就(return) (true)。如果一直没有(return)，那么就不可行。
只写了思路二的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define mid ((l+r)>>1)
#define midd ((ll+rr)>>1)
using namespace std;
const LL N = 100005;
LL n,D,maxx,minn=1000006,l=1,r;
LL maxxl,minnl=1000006,ans;
struct node{
LL x,y;
bool friend operator < (const node& a,const node& b)
{ return a.x<b.x; }
}a[N],q[N];
LL aaa[40000000];
inline int read()
{
int ans=0,w=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-') c=getchar();
if(c=='-') { w=-1; c=getchar(); }
while(c>='0'&&c<='9')
{ ans=ans*10+c-'0'; c=getchar(); }
return ans*w;
}
bool check(LL u)
{
l=1,r=0;
for(LL i=1;i<=n;i++)
{
while(q[r].y<=a[i].y&&r) --r;
LL ll=1,rr=r,ansp=-1;
while(ll<=rr)
{
if(a[i].x-q[midd].x<=u) ansp=midd,rr=midd-1;
else ll=midd+1;
}
if(q[ansp].y-a[i].y>=D&&ansp>0) return true;
q[++r].x=a[i].x;
q[r].y=a[i].y;
}
l=1;r=0;
for(LL i=n;i>=1;i--)
{
while(q[r].y<=a[i].y&&r) --r;
LL ll=1,rr=r,ansp=-1;
while(ll<=rr)
{
if(q[midd].x-a[i].x<=u) ansp=midd,ll=midd+1;
else rr=midd-1;
}
if(q[ansp].y-a[i].y>=D&&ansp>0) return true;
q[++r].x=a[i].x;
q[r].y=a[i].y;
}
return false;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
// cin>>n>>D;
// scanf("%lld%lld",&n,&D);
n=read(); D=read();
for(LL i=1;i<=n;i++)
{
scanf("%lld%lld",&a[i].x,&a[i].y);
minn=min(minn,a[i].y);
maxx=max(maxx,a[i].y);
minnl=min(minnl,a[i].x);
maxxl=max(maxxl,a[i].x);
}
// cout<<maxx<<"*"<<minn<<endl;
if(maxx-minn<D) { printf("-1
"); return 0; }
sort(a+1,a+n+1);
LL l=1,r=maxxl-minnl;
ans=r;
while(l<=r)
{
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld
",ans);
return 0;
}
写完另一个算法，又回来改了半天，还是没改对，虽然感觉是和另一个算法一样的错误。
题解思路：二分出一个(L)，求从左到右每一个长度为(L)的区间中的最大值和最小值（滑动窗口），看是否有满足条件的。
第一次交的时候90分：
100分：
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int N = 100005;
const int inf = 2147483647;
int n,D,l1=1,r1,l2=1,r2;
int ans,min1=inf,min2=inf,max1,max2;
struct node{
int x,y;
// bool friend operator <(const node& a,const node& b)
// { return a.x<b.x; }
}a[N],q1[N],q2[N];
bool cmp(node a,node b)
{ return a.x<b.x; }
bool check(int u)
{
l1=l2=1; r1=r2=0;
for(int i=1;i<=n;i++)
{
while(l1<=r1&&a[i].x-q1[l1].x>u) ++l1;
while(l2<=r2&&a[i].x-q2[l2].x>u) ++l2;
while(q1[r1].y<=a[i].y&&r1) --r1;
while(q2[r2].y>=a[i].y&&r2) --r2;
q1[++r1].x=a[i].x; q1[r1].y=a[i].y;
q2[++r2].x=a[i].x; q2[r2].y=a[i].y;
if(q1[l1].y-q2[l2].y>=D) return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&D);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
min1=min(min1,a[i].x);
min2=min(min2,a[i].y);
max1=max(max1,a[i].x);
max2=max(max2,a[i].y);
}
if(max1-min1<D) { printf("-1
"); return 0 ;}
sort(a+1,a+n+1,cmp);
int l=1,r=max1-min1;
while(l<=r)
{
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d
",ans);
return 0;
}