136. 邻值查找

给定一个长度为 nn 的序列 AA，AA 中的数各不相同。

对于 AA 中的每一个数 AiAi，求：

min1≤j<i|Ai−Aj|min1≤j<i|Ai−Aj|

以及令上式取到最小值的 jj（记为 PiPi）。若最小值点不唯一，则选择使 AjAj 较小的那个。

输入格式

第一行输入整数 nn，代表序列长度。

第二行输入 nn 个整数A1…AnA1…An,代表序列的具体数值，数值之间用空格隔开。

输出格式

输出共 n−1n−1 行，每行输出两个整数，数值之间用空格隔开。

分别表示当 ii 取 2∼n2∼n 时，对应的 min1≤j<i|Ai−Aj|min1≤j<i|Ai−Aj| 和 PiPi 的值。

数据范围

n≤105n≤105,|Ai|≤109|Ai|≤109

输入样例：

3
1 5 3

输出样例：

4 1
2 1

题解：

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args)throws Exception {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long a[] = new long[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();
        }

        TreeMap<Long, Integer> TreeMap = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                //获取到long最大值
                long minn = Long.MAX_VALUE;
                //pos为下标
                int pos = -1;

                //找到最小大于a[i]的数
                Map.Entry<Long,Integer> upper = TreeMap.ceilingEntry(a[i]);
                //找到最大小于a[i]的数
                Map.Entry<Long,Integer> lower = TreeMap.floorEntry(a[i]);
                
                //需要先判断最大小于a[i]的数
                if (lower != null && Math.abs(lower.getKey() - a[i]) < minn){
                    minn = Math.abs(lower.getKey() - a[i]);
                    pos = lower.getValue();
                }
                if (upper != null && Math.abs(upper.getKey() - a[i]) < minn){
                    minn = Math.abs(upper.getKey() - a[i]);
                    pos = upper.getValue();
                }

                System.out.println(minn +" "+(pos+1));

            }
            //判断Map中是否存在当前值，不存在则添加进去
            if (!TreeMap.containsKey(a[i])) TreeMap.put(a[i], i);
        }

    }
}