思路

• 给原数组排下序 记录下他们之间的关系
• 这样 求前驱就变为了
• 对于每一个数 在排序后数组中 找到在他前面 离他最近的 排序前下标 小于他的数
• 后继同理
• 对于 找到离他最近的 排序前下标 小于他的数 我们可以使用单调栈

做法:

• 给原数组排下序 记录下他们之间的关系
• 用单调栈求出 离他最近的 排序前下标 小于他的数 l[i] r[i]
• 扫一遍 得出答案

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 100010;
const LL INF = 4e9;

int n;
int l[N], r[N], p[N];
PLI a[N];
int q[N], tt;


int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &a[i].first);
        a[i].second = i;
    }

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++ )
        p[a[i].second] = i;

    a[0].first = -INF, a[n + 1].first = -INF;
    q[0] = 0; //哨兵不加也可以 因为 0 n + 1默认是0
    for (int i = 1; i <= n; i ++ )
    {
        int v = a[i].second;
        while (a[q[tt]].second >= v) tt -- ;
        l[i] = q[tt];

        q[ ++ tt] = i;
    }

    tt = 0;
    q[0] = 0;
    for (int i = n; i >= 1; i -- )
    {
        int v = a[i].second;
        while (a[q[tt]].second >= v) tt -- ;
        r[i] = q[tt];

        q[ ++ tt] = i;
    }

    for (int i = 2; i <= n; i ++ )
    {
        int j = p[i], left = l[j], right = r[j];
        //printf("%d %d %d\n", j, left, right);
        LL lv = abs(a[j].first - a[left].first);
        LL rv = abs(a[right].first - a[j].first);

        if (lv <= rv) printf("%lld %d\n", lv, a[left].second);
        else printf("%lld %d\n", rv, a[right].second);
    }

    return 0;
}

$附3种解法的代码$

https://www.acwing.com/activity/content/code/content/6502350/