用到了 数组实现的链表， 双向链表

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
int n, m;
pair<int, int> a[maxn]; //输入的值与他的位置
pair<int, int> ans[maxn];   //每个结果差最大的，和他的位置
int l[maxn], r[maxn], p[maxn];
//左边的位置，右边的位置， 与自身的位置

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a+1, a+1+n);
    a[0].first = INT_MAX; //设置两个边界，设置成最大，因为题意要求最小的差
    a[n+1].first = INT_MAX;

    for(int i = 1; i <= n; i ++)
    {
        l[i] = i-1; r[i] = i + 1; //已经排序完成了，每个数字的左右表示出来
        p[a[i].second] = i;       //排完序之后，排第i的数字原来的位置要标记到p的第i个位置
    }                               //这里是最绕的，因为我们之后要用到的是原来的位置，所以要标记原位置

    //从n开始 是因为要求每个数字左边的数字，从最大值开始，左右数字都小于最大值
    for(int i = n; i >= 1; i --)
    {
        int j = p[i];       //用j 来表示排最大的数字的原来的位置
        int left = l[j], right = r[j];  //left 是原来最大数字左边， 同理右边
        int lv = abs(a[j].first - a[left].first);   //lv是当前最大数字与原位置左边数字的差
        int rv = abs(a[j].first - a[right].first);  //同理

        if(lv <= rv) ans[i] = {lv, a[left].second}; //如果左边小，记录左边的值，记录左边值原来的位置
        else ans[i] = {rv, a[right].second};    //否则右边

        r[left] = right; //链表的删除操作
        l[right] = left;
    }

    for(int i = 2; i <= n; i ++)
        cout << ans[i].first << " " << ans[i].second << endl; //按顺序输出
    return 0;
}