邻值查找

package main

import (
    "fmt"  
    "sort"
)

// node 双向链表节点。
type node struct {
    idx  int
    val  int
    pre  *node
    next *node
}

// addNode 在 head 后插入节点 newNode。
func addNode(head, newNode *node) {
    newNode.next = head.next
    newNode.pre = head
    head.next.pre = newNode
    head.next = newNode
} 

// deleteNode 删除节点。
func deleteNode(node *node) {
    node.pre.next = node.next
    node.next.pre = node.pre
}

func main() {
    // 保存输入的数组长度
    var n int
    fmt.Scanf("%d", &n)
    
    // 因为题目要求的下标从一开始，所以申请 n + 1 的数组长度
    // a 数组用作保存输入数组
    a := make([]int, n + 1)
    // rk 保存数组 a 排序后的下标，也就是 a[rk[i]] 的结果是升序的
    rk := make([]int, n + 1)
    // 遍历保存每一个数组元素
    for i := 1; i <= n; i++ {
        fmt.Scanf("%d", &a[i])
        rk[i] = i
    }
    
    // 自定义排序算法，使得 a[rk[i]] 的结果升序
    sort.Slice(rk[1:], func(i, j int) bool {
        return a[rk[i + 1]] < a[rk[j + 1]]
    })
    
    
    // 定义双向链表
    // 选在在最小节点减 1e10，最大节点加 1e10 是因为防止在相邻节点计算时选到头尾节点
    // 也可以选择用 1e9 + 1 代替 1e10
    head, tail := &node{val: a[rk[1]]  - 1e10}, &node{val: a[rk[n]] + 1e10}
    head.next, tail.pre = tail, head
    
    // 定义一个 map，key 为数组 a 下标，val 为对应的节点指针地址
    mp := make(map[int]*node, n)
    
    // 遍历 rk，将 rk[i] 顺序插入链表
    // 插入后，链表从 head 到 tail， val 的值都递增
    for i := n; i >=1; i-- {
        idx := rk[i]
        cur := &node{
            idx: idx,
            val: a[idx],
        }
        mp[idx] = cur
        addNode(head, cur)
    }
    
    res := make([]int, n + 1)
    
    // 从后往前遍历数组，每次使用后将对应的链表节点删除
    // 因为根据题意，后面的数组元素不能影响前面的数组元素
    for i := n; i > 1; i-- {
        // 取出当前节点
        cur := mp[i]
        // 根据题意选择一个和当前值相减绝对值最小的
        // 因为链表已经按顺序排列了，所以只要相邻节点相减
        // 如果减出来绝对值都一样，则选择较小的那个值（由题意得）
        if cur.val - cur.pre.val <= cur.next.val - cur.val {
            res[i] = cur.pre.idx
        } else {
            res[i] = cur.next.idx
        }
        deleteNode(cur)
        delete(mp, i)
    }
    
    // 输出结果
    for i := 2; i <=n; i++ {
        fmt.Println(abs(a[res[i]] - a[i]), res[i])
    }
}

// abs 绝对值。
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}