LeetCode 1200. 最小绝对差

2023-10-20 HGNULB 约 7 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1200. 最小绝对差

题意分析

给一个各元素互不相同的整数数组 arr，先求出任意两个元素之间绝对差的最小值，再把所有达到这个最小差值的数对全部列出来。每个数对写成 [较小值, 较大值]，并且整个结果要按升序排列。

要点一：答案不是一个数而是一组数对，所以不能只求出最小差就返回，必须再把所有取到它的组合收集齐。达到最小差的数对可能有很多，例如 [1,2,3,4] 中差为 1 的对有三组。

要点二：输出有顺序要求——数对内部升序、数对之间也升序。这条约束会影响实现方式：如果先收集再排序会多一次开销，而下面的做法能让顺序天然正确。

要点三：元素互不相同，所以最小差一定大于 0，不必考虑差为 0 的重复元素。

约束：arr 长度上限 $10^5$，元素范围是 $[-10^6, 10^6]$。$n^2 = 10^{10}$ 的两两枚举不可行，这个规模指向排序（$O(n \log n)$）或值域计数（$O(V)$）。注意负数的存在——用值域数组时要做偏移。

边界：arr 至少有 2 个元素，所以答案非空；元素跨越正负时相减的绝对值最大约 $2 \times 10^6$，int 完全够用，不会溢出。

解法：排序 + 一次扫描

核心思路

先看暴力：双重循环枚举所有 $\binom{n}{2}$ 个数对，先求最小差再收集。$n = 10^5$ 时约 $5 \times 10^9$ 次比较，必然超时。瓶颈在于绝大多数数对根本不可能成为答案——两个相差很远的数被反复计算了。

关键观察：把数组排好序之后，绝对差最小的两个数一定是相邻的。

证明很直接：设排序后有 $i < j$ 且 $j - i \ge 2$，那么中间必然存在下标 $t$ 满足 $i < t < j$，于是 $a_j - a_i = (a_j - a_t) + (a_t - a_i)$，两个加项都为正（元素互不相同），因此 $a_j - a_i$ 严格大于其中任何一个——不相邻的数对总能被更近的数对超越。所以候选从 $O(n^2)$ 对锐减到 $n - 1$ 对相邻对。

排序还顺带解决了输出顺序问题：升序数组中相邻对 (arr[i-1], arr[i]) 本身就是「小在前、大在后」，而按 i 递增的顺序收集出来的数对序列也自动满足字典序升序。顺序不用额外处理，这是选择「排序后按下标扫描」而非「哈希收集后再排」的实际好处。

排序后只需扫描一次相邻对。维护当前最小差 minDiff 和所有达到该差值的答案：遇到更小差值时更新 minDiff 并清空旧答案；遇到等于 minDiff 的差值时加入当前数对。

扫描不变量：处理完前 i 个相邻对后，minDiff 是其中的最小差，结果恰好包含其中所有差等于 minDiff 的数对。新差更大时状态不变；相等时追加；更小时旧答案全部失效，清空后加入新数对，因此不变量始终成立。扫描结束时，所有候选都已处理，结果就是完整答案。

排序后 arr[i] - arr[i-1] 恒为正，可以直接作为绝对差，不需要 Math.abs。

解题步骤

排序：Arrays.sort(arr)。这是全部推理的前提，没有它「最小差在相邻对之间」不成立。原地排序不需要额外数组。

初始化状态：minDiff = Integer.MAX_VALUE，答案为空。数组至少有两个元素，所以第一个相邻差一定会刷新初值。

直接相减而不取绝对值：排序后 arr[i] >= arr[i-1]，差值必然非负。省掉 Math.abs 不只是省一次调用，更是在提醒读者「这里已经有序」。

一次扫描并维护答案：从 i = 1 开始计算相邻差。若 diff < minDiff，更新最小差并清空此前答案；随后若 diff == minDiff，加入 [arr[i-1], arr[i]]。这里用两个独立的 if，保证刚刷新最小差的当前数对也会被加入。

按下标递增收集：结果列表天然按第一个元素升序排列，不需要再对结果做一次排序。

返回结果。因为至少有两个元素，minDiff 一定被某个相邻对取到，结果不会为空。

以 arr = [4, 2, 1, 3] 走一遍（答案 [[1,2],[2,3],[3,4]]）：

排序后 arr = [1, 2, 3, 4]。

扫描到 [1,2] 时把 minDiff 更新为 1，清空空列表并加入 [1,2]；之后两个相邻差也都是 1，依次追加 [2,3]、[3,4]。结果天然有序。

再以 arr = [1, 3, 6, 10, 15] 走一遍（答案 [[1,3]]）：

已经有序。第一个差值 2 刷新最小差并加入 [1,3]，后续差值 3、4、5 都更大，状态不变。注意 1 与 6 的差是 5、3 与 10 的差是 7——每个非相邻对都包含更小的相邻差，这就是「只看相邻对」的正确性来源。

再以 arr = [3, 8, -10, 23, 19, -4, -14, 27] 走一遍（答案 [[-14,-10],[19,23],[23,27]]）：

排序后 [-14, -10, -4, 3, 8, 19, 23, 27]，相邻差依次是 4、6、7、5、11、4、4。扫描先加入 [-14,-10]，最后再追加 [19,23]、[23,27]。负数在这里没有特殊分支——排序后相减仍为正。

若忘记排序，直接在原数组 [3, 8, -10, ...] 上扫相邻对，第一个差就是 8-3 = 5，而 -10 - 8 = -18 是负数，minDiff 会变成 -18，结果收集到的是一堆毫无意义的数对。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);

        List<List<Integer>> ans = new ArrayList<>();
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            int diff = arr[i] - arr[i - 1];
            if (diff < minDiff) {
                minDiff = diff;
                ans.clear();
            }
            if (diff == minDiff) {
                ans.add(Arrays.asList(arr[i - 1], arr[i]));
            }
        }
        return ans;
    }
}

import "sort"

func minimumAbsDifference(arr []int) [][]int {
	sort.Ints(arr)

	ans := make([][]int, 0)
	minDiff := int(^uint(0) >> 1)
	for i := 1; i < len(arr); i++ {
		diff := arr[i] - arr[i-1]
		if diff < minDiff {
			minDiff = diff
			ans = ans[:0]
		}
		if diff == minDiff {
			ans = append(ans, []int{arr[i-1], arr[i]})
		}
	}
	return ans
}

复杂度分析

时间复杂度：$O(n \log n)$，排序主导；排序后的一次扫描是 $O(n)$。

空间复杂度：不计返回结果，原地排序的辅助空间为 $O(\log n)$；结果最坏包含 $n-1$ 个数对，占 $O(n)$。

关键点总结

「最小差一定在相邻元素之间」是排序带来的核心结论：不相邻的两数之差总能被它们之间的某个相邻对超越，候选从 $O(n^2)$ 降到 $O(n)$。能把这个一句话的证明说清楚，是这道题的主要考点。

排序不仅压缩了候选，还免费解决了输出顺序：升序数组中按下标递增收集，数对内与数对间的升序自动成立。识别出「排序顺带满足了另一个约束」，能省掉一次额外排序。

有序后相减必为非负，Math.abs 可以并且应该省掉——多余的调用会掩盖「这里已经有序」这个前提。

扫描时维护「当前最小差 + 对应的全部数对」：更小就清空，相等就追加。两个独立 if 能让刷新最小差的当前数对立即入选。

minDiff 取类型最大值，配合数组至少有两个元素的约束，第一次比较必然刷新，无需单独处理第一对。

易错点总结

错误写法：忘记排序直接扫相邻对。用例 arr = [3, 8, -10, 23]：-10 - 8 = -18，minDiff 变成负数，收集到的数对完全无意义。

错误写法：找到第一个最小差数对就停止。用例 arr = [1,2,3,4] 会只返回 [[1,2]]，漏掉另外两对。

错误写法：循环从 i = 0 开始却访问 arr[i-1]，会在第一次迭代访问下标 -1。

错误写法：一遍扫描时遇到更小差值只更新 minDiff 而不清空已收集的结果。用例 arr = [1, 100, 101, 102]：先按差 99 收了 [1,100]，之后遇到差 1 更新了 minDiff 却没清空，返回 [[1,100],[100,101],[101,102]]，混入了非最优对。

错误写法：minDiff 初值取 0。元素互不相同，所有相邻差都大于 0，最小差永远无法刷新，答案会为空。

错误写法：用 Math.abs 弥补未排序。用例 arr = [10,1,9] 只比较原数组相邻位置会得到最小差 8，仍会漏掉真实答案 [9,10]。

相似题目

题目	难度	考察点
530. 二叉搜索树的最小绝对差	简单	同一结论换到 BST 上，中序遍历即得有序序列，比较相邻两个节点
783. 二叉搜索树节点最小距离	简单	与 530 同题不同表述，可用于巩固「有序序列看相邻」的模式
164. 最大间距	中等	求相邻最大间距且要求线性时间，必须用桶排序 + 鸽巢原理
539. 最小时间差	中等	排序后比相邻，但时间是环形的，还要额外比较首尾跨天的一对
217. 存在重复元素	简单	相当于判断最小差是否为 0，排序与哈希两种思路的对照
2300. 咒语和药水的成功对数	中等	排序后用单调性把 $O(n^2)$ 配对降为二分，与本题同属「排序压缩候选」