刷题痛苦


一开始，我也不会。通过看他人提交通过代码。解题方案：
1. 单调队列。
2.二分法。

以下主要解释内存排行榜单上面的单调队列方法。
单调队列可以有两种解法：
1.对 H 数组进行 正反 两次遍历，构建两次单调递增的队列。
2正向循环遍历一次，构建一次单调递增队列。（内存榜单上的主流代码是这种解法，但存在缺陷。）以下会对代码进行解释。

原代码原理：

第一个while循环判断// 每次元素的填入是从队尾填入 需要保证队列的单调递增;  
  判断解释（队尾>=队首的位置，并且队尾（队列中y值最大）元素的 y 值 >= 当前循环元素 A[ i ] 的 y 值 .
为保证队列的单调性我们应该删除队尾元素，即 tail - -;   (但是如果仅仅如此，代码是有缺陷的)

缺陷：

缺陷就是我们只能判断 一种情况即，i <j , A[ i ].y<A[ j ] 的情况 （排序后数组中 左 小 右 大 的情况）
而没有i <j , A[ i ].y>A[ j ] 排序后数组中 左 大 右 小 的情况）

可以用以下案例证明其缺陷 (由案例简单修改获得，红色数字为修改处
1）
3 5
6 3
4 10
12 15 
答案应该为 2
2)
4 5
5 3
2 4
4 10
12 15  
答案应该为 1

修改方案：

1. 加一次反向循环遍历，循环内容与原循环结构相同，以判断 左大右小 的情况。
2. 利用在 队尾删除 之前，添加元素 A[ i ] 与 队尾元素  dl[ tail ]之间 形成类似 左大右小 的情况，进行缺陷的补足。

//第一个代码       单调队列的模拟 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<string>
#include<queue>
#include<deque>
#include<set>
using namespace std;
typedef long long ll;

int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

int N,D;
struct pp{
	int x,y;
}A[100010],dl[100010];

bool cmp(pp l,pp r){
	return l.x<r.x;
}

int main(){
	cin>>N>>D;
	for(int i=1;i<=N;i++){
		A[i].x=read(),A[i].y=read();
	}
	sort(A+1,A+N+1,cmp);//以x值从小到大进行排序
	int head=1,tail=0;//head 队首下标，tail为队尾下标（因为这个时候队列元素为空，不能把tail初始化为1）
	int ans=1e9;
	for(int i=1;i<=N;i++){ //模拟以y值大小为判断单调递增队列 
		while(head<=tail&&dl[tail].y>=A[i].y){
            if(dl[tail].y-A[i].y>=D){//该判断为 出现 左大右小 处理
                ans=min(ans,A[i].x-dl[tail].x);
            }
            tail--;//队尾的删除
        }
        
		dl[++tail]=A[i];  //新的最大队尾 
		while(dl[tail].y-dl[head].y>=D) ans=min(ans,dl[tail].x-dl[head++].x);//新队尾 和 队首的 y 的差值判断。
	}
	if(ans>=1e9) cout<<-1;
	else cout<<ans;
	return 0;
}
 
// 第二个代码 直接用双端队列 构成单调队列，（该代码为 我好友 的代码） 
#include<bits/stdc++.h>
using namespace std;
#define pai pair<int,int>
#define x first
#define y second
const int N=1e5+10;
pai a[N];
deque<pai>de;
int n,d;
int main()
{
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+n);
    int ans=1e9;
    for(int i=1;i<=n;i++)
    {
        while(!de.empty()&&a[i].y<=de.back().y)
        {
            if(de.back().y-a[i].y>=d)
                ans=min(ans,(a[i].x-de.back().x));
            de.pop_back();
        }
        while(!de.empty()&&(a[i].y-de.front().y)>=d)
            {ans=min(ans,(a[i].x-de.front().x));
            de.pop_front();}
        de.push_back(a[i]);
    }
    if(ans==1e9)cout<<-1;
    else cout<<ans;
}