AcWing 136. 邻值查找
原题链接
中等
作者:
编号002
,
2024-07-25 11:55:16
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],n,a[N];
map<int,int> ind,newi;
stack<int> c,b;
void remove(int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
ind[a[i]]=i; //原下标
}
sort(a+1,a+n+1); //排序后一个数两端的值肯定有一个答案
for(int i=1;i<=n;i++)
newi[ind[a[i]]]=i; //旧坐标对应的新坐标
//将数组转化为链表
r[0]=n+1,l[n+1]=0;
for(int i=1;i<=n;i++)
{
l[i]=i-1;
r[i]=i+1;
e[i]=a[i];
}
//逆序遍历原数组,并将其删除,可以保证答案的下标一定合法
for(int i=n;i>1;i--)
{
int k=newi[i],ans,ans_i;
bool flag=0;
//边界问题
if(l[k]!=0)
{
ans=abs(e[k]-e[l[k]]);
ans_i=ind[e[l[k]]];
flag=1;
}
if(r[k]!=n+1)
{
int t=abs(e[k]-e[r[k]]);
if(!flag||flag&&t<ans)
{
ans=t;
ans_i=ind[e[r[k]]];
}
}
remove(k);
c.push(ans);
b.push(ans_i);
}
while(c.size())
{
cout<<c.top()<<' '<<b.top()<<endl;
c.pop();
b.pop();
}
return 0;
}