LeetCode 1200. 最小绝对差

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 拼多多
标签
数组 排序

题目描述

✅ 1200. 最小绝对差

image-20260929075308730

image-20260929075308812

题意分析

从元素互不相同的整数数组中，找出所有绝对差等于全局最小值的数对。每对内部按小值在前、大值在后排列，所有数对也按升序返回，不能只返回差值或任意一对。

题目保证至少有两个元素，因此一定存在答案。数对由数组中的值组成，不要求它们在原输入中相邻；同一个元素可以分别参与不同的最优数对。

解法：排序 + 一次扫描

核心思路

[!blue]

先把数组升序排序。任意两个不相邻的数之间至少夹着一个介于两者之间的数，它们的差等于若干个相邻差之和；由于值互不相同，这些相邻差都为正，所以不相邻差严格大于其中每一个相邻差，不可能是全局最小值。候选因此只剩 n - 1 个有序相邻对。

从左到右扫描相邻差，维护当前最小值 minDiff 和所有达到它的候选数对。遇到更小差时，之前收集的对已经不是最优，应先清空，再记录当前对；遇到相等差时追加；更大差则忽略。

代码使用两个独立的判断：第一个在差更小时更新最小值并清空，第二个检查差是否等于更新后的最小值，从而把刚刷新最优的当前对也加入。如果改成互斥的两个分支，却没有在刷新分支里添加当前对，就会漏掉它。

每对直接取排序后的前后两项，内部已经升序；扫描时左值也不断增大，因此追加得到的数对顺序自然符合输出要求，不需要额外再排序答案。

解题步骤

  1. 原地升序排序数组，初始化最小差为足够大的值，结果列表为空。
  2. 从第二个元素开始，计算它与前一个元素的差。
  3. 差比当前最小值更小时，更新最小差并清空旧数对。
  4. 继续独立检查差是否等于当前最小值，满足就加入这一对。
  5. 扫描完所有相邻位置，返回结果。

代码实现

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)$，包含最多线性数量的候选数对和结果容器；清空列表或缩短切片不保证立即释放此前容量。

关键点总结

[!green]

  • 有序非相邻差由多个正相邻差组成，所以只检查相邻值就能找全最优数对。
  • 新的更小差使旧候选全部失效，同差则继续累加。
  • 刷新后仍需加入当前对，两个独立判断完整覆盖这一过程。
  • 排序后的扫描顺序同时满足数对内部与数对之间的顺序要求。

易错点总结

[!yellow]

  • 不排序就只比较原位置相邻元素，会漏掉数值接近但原位置相隔很远的一对。
  • 找到更小差后不清空旧结果，会混入不再达到全局最小差的数对。
  • 直接将第二个判断改成 else if，又未在第一个分支追加，会漏掉首次达到新最小差的当前对。
  • 最小差初始化为零，互异元素的正差都无法刷新，结果可能一直为空。
  • 把返回目标当成只有一对，遇到相同最小差时不再追加，会少返回合法答案。

相似题目

题目 难度 关联与区别
530. 二叉搜索树的最小绝对差 简单 最小绝对差都来自有序相邻值，本题先排序数组，原题用BST中序顺序。
面试题 16.06. 最小差 中等 原题从两个数组各取一个值，需要双指针保证来源不同，本题比较同一数组相邻项。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/11580534
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！