136.邻值查找

Acwing

双向链表

用排序后的双向链表维护每个数字前后相邻的两个数字用来计算最大绝对值。

计算绝对值时根据原数组顺序从后往前遍历，处理完后则在链表中删除当前数字。

时间复杂度：O(N)
空间复杂度：O(N)

package main

import (
    "fmt"
    "sort"
)

type Node struct {
    Prev *Node
    Next *Node
    Val int
    Index int
}

func main() {
    var n int
    fmt.Scan(&n)
    
    nums := make([][]int, n)
    
    for i := 0; i < n; i++ {
        nums[i] = make([]int, 2)
        fmt.Scanf("%d", &nums[i][0])
        nums[i][1] = i
    }
    
    sort.Slice(nums, func(i, j int) bool {
        return nums[i][0] < nums[j][0]
    })
    
    head := &Node{
        Index: -1,
    }
    prev := head
    nodes := make([]*Node, n)
    ans := make([][]int, n)
    
    for i := 0; i < n; i++ {
        node := &Node{
            Prev: prev,
            Val: nums[i][0],
            Index: nums[i][1],
        }
        
        prev.Next = node
        prev = node
        nodes[nums[i][1]] = node
        // fmt.Printf("%v, %v\n", nums[i][1], node)
    }
    
    prev.Next =  &Node{
            Index: n,
        }
    
    for i := n - 1; i > 0; i--{
        curr := nodes[i]
        pn := nodes[i].Prev
        nn := nodes[i].Next
        

        ans[i] = make([]int, 2)
        // fmt.Printf("%v %v %v\n", p.Val, curr.Val, n.Val)
        if nn.Index == n || (pn.Index != -1 && abs(pn.Val - curr.Val) <= abs(nn.Val - curr.Val)) {
            ans[i][0] = abs(pn.Val - curr.Val)
            ans[i][1] = pn.Index + 1
        } else {
            ans[i][0] = abs(nn.Val - curr.Val)
            ans[i][1] = nn.Index + 1
        }
        
        pn.Next = curr.Next
        nn.Prev = pn
    }
    
    for i := 1; i < n; i++ {
        fmt.Printf("%v %v\n", ans[i][0], ans[i][1])
    }
    
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}