LeetCode 1200 这道题，我前前后后刷了不止一遍，面过别人也被问过。题目名字叫 Minimum Absolute Difference，中文社区一般叫“最小绝对差”，难度标的是 Easy，但如果把它当成一道“看一遍就会”的题直接跳过，其实挺亏的。原因很简单：这道题虽然代码量不大，但它把“排序 + 相邻性”这个套路讲得特别清楚，而这个套路往后再遇到“最小差值系列”“区间查询系列”都会反复出现。这篇就围绕 LeetCode 1200 把题目拆开揉碎，从暴力思路一路推到最优解，再聊几个实战里容易栽的细节，最后把它和几道热门题放一起对比一下，帮你彻底吃透这一类问题。
1. 题目拆解与考点分析
1.1 题目到底在问什么
先说结论：给你一个整数数组arr，数组里的元素互不相同，然后你要找出“差的绝对值最小”的那些数对，按升序返回。
比如arr = [4, 2, 1, 3]，先把数组排序变成[1, 2, 3, 4]。相邻数字之间差的绝对值全是 1，这就是全局最小差，所以答案要输出[[1,2],[2,3],[3,4]]。再比如arr = [3, 8, -10, 23, 19, -4, -14, 27]，排序后是[-14, -10, -4, 3, 8, 19, 23, 27]，相邻差最小是 4，出现在-14 和 -10、19 和 23、23 和 27这三对，答案就是[[-14,-10],[19,23],[23,27]]。
这里有几个容易被忽略的限定条件。其一是元素互不相同，这意味着最小绝对差最小也就是 1，不可能出现 0 的情况。其二是返回的数对内部要升序，外层集合也要升序，不过只要你基于排序后的数组从左往右扫描，这两个“升序”其实都是自动保证的。其三是数组长度范围，题目里给的是2 <= arr.length <= 10^5，元素值范围是-10^6 <= arr[i] <= 10^6。这个数据规模很关键，它决定了暴力枚举一定会超时，也决定了最优解必须落在O(n log n)或者更优的复杂度上。
1.2 这道题背后真正考的是什么
表面上看，这道题考的是“求相邻元素差值”这种基本功，但实际上它考的是三个递进的点：
第一，知不知道要先排序。数组乱序时，两个数值接近的元素可能相隔很远，不排序根本没法高效地找“全局最小差”。先排序是这类问题的第一反应，也是后面所有推导的前提。
第二，能不能证明“最小差只可能出现在相邻元素之间”。很多人凭直觉觉得排序后检查相邻就行，但面试官如果追问一句“为什么不相邻的那对不可能更小”，你需要给出严谨的说法。这个证明不复杂，我用反证法说一遍：假设数组排序后是a[0] <= a[1] <= ... <= a[n-1]，如果最优解出现在不相邻的a[i]和a[j]之间，并且j - i >= 2，那么中间一定存在某个元素a[i+1]。由于a[i] <= a[i+1] <= a[j]，所以a[i+1] - a[i] <= a[j] - a[i]。也就是说，这对不相邻元素的差值不可能比它“中间夹着”的相邻差值更小。如果它真的是全局最小，那么夹着的相邻对至少不会比它大，也就是说全局最小一定会在相邻对中重新出现。于是结论成立：全局最小绝对差一定藏在排序后某个相邻对里。
第三，能不能把“找最小值”和“收集结果”合并成一轮扫描。这是从 Easy 到“能给别人讲明白”的分水岭。很多人写出了两轮循环的版本也能过，但一轮扫描的写法更干净，而且能体现你对状态更新的理解——什么时候清空结果集，什么时候追加结果集，这个分寸感比背代码重要得多。
2. 从暴力到最优：解题思路的完整推导
2.1 暴力枚举为什么走不通
先看最直觉的做法。对每一个下标i，再枚举所有j > i，计算abs(arr[i] - arr[j])，记录全局最小值，第二遍再枚举一次，把所有差值等于最小值的数对收集起来。这个思路完全正确，没有任何逻辑问题，唯一的致命伤是复杂度。
n = 10^5时，数对数量大约是n * (n-1) / 2 = 5 * 10^9。假设你的机器每秒能跑10^8次简单运算，光枚举这些数对就要 50 秒，这还没算abs调用和结果集操作的开销。放到 LeetCode 的评测环境里，这基本是必超时的状态。就算你把n降到10^4，5 千万次计算也很悬。
所以这道题的第一课是：看到10^5这种规模，就要条件反射地排除O(n^2)。排序的O(n log n)在这个规模下大概只有10^5 * 17次基础操作，和 50 亿完全不是一个量级。
2.2 排序之后的关键洞察：相邻对就够了
排序带来的好处不止是数值有序，更重要的是它天然把“距离近”的候选对象压缩到了相邻位置。
你可能会想：排序后[1, 3, 5, 6]，最小差显然是 1，出现在5和6这对相邻数之间。但如果数组是[1, 4, 10, 12]，最小差是 2，出现在10和12，它俩还是相邻的。再试几个例子会发现，排序后每个数只跟它的左邻居或右邻居比就够了，跨过中间元素去比较，差值只可能更大，不可能更小，原因前面用反证法已经说过了。
这个洞察的价值在于：它将原本“任意两两组合”的问题，降维成了“只处理n-1个相邻间隔”的问题。排序是O(n log n)，处理间隔是O(n)，整体就是O(n log n)。这就是从O(n^2)到O(n log n)的本质飞跃。
2.3 两轮扫描和一轮扫描的演进过程
最简单的实现是两轮扫描：第一轮算出最小差值，第二轮收集所有等于这个差值的相邻对。
// C++ class Solution { public: vector<vector<int>> minimumAbsDifference(vector<int>& arr) { sort(arr.begin(), arr.end()); vector<vector<int>> ans; int mn = INT_MAX; for (int i = 1; i < arr.size(); ++i) { mn = min(mn, arr[i] - arr[i - 1]); } for (int i = 1; i < arr.size(); ++i) { if (arr[i] - arr[i - 1] == mn) { ans.push_back({arr[i - 1], arr[i]}); } } return ans; } };这个版本可读性很好，逻辑也清晰。但如果你仔细观察，会发现第二轮循环遍历的时候，其实第一轮已经把所有相邻差值都算过一遍了。能不能一边算一边更新结果呢？当然可以，而且这个优化很有意思。
想象你手里有一个变量minDiff，它记录“到目前为止发现的最小差值”，还有一个结果集ans。当你在扫描中算出一个新的差值diff时，有三种情况：
diff < minDiff：发现了一个更小的差值，那么之前收集的所有结果全部作废，清空ans，把当前这对放进去，同时更新minDiff = diff；diff == minDiff：又找到一对和当前最小差值相等的，直接追加进ans；diff > minDiff：这个差值太大，什么也不用做。
这样一轮走完，ans里自然就是所有最小差值的相邻对。这就是下面这版一次扫描的实现，也是我最推荐的写法，因为它把“候选最小值的更新”和“结果集的重建”用同一个循环完成了，代码更紧凑，而且能直接看出你对这个状态机的理解。
class Solution { public: vector<vector<int>> minimumAbsDifference(vector<int>& arr) { sort(arr.begin(), arr.end()); vector<vector<int>> ans; int mn = INT_MAX; for (int i = 1; i < arr.size(); ++i) { int diff = arr[i] - arr[i - 1]; if (diff < mn) { mn = diff; ans.clear(); ans.push_back({arr[i - 1], arr[i]}); } else if (diff == mn) { ans.push_back({arr[i - 1], arr[i]}); } } return ans; } };如果你刚开始学，第一版更好懂；如果你已经有一定基础了，建议直接写第二版。两版的时间复杂度都是O(n log n)，但面试时如果能写出第二版，并且把“为什么diff < mn时要清空”讲清楚，绝对会是加分项。
3. 代码实现与细节剖析
3.1 三种主流语言的实现对比
这道题几乎每种语言都能写得很短，但细节取舍不太一样。我把 C++、Java、Python 三个版本都放在这里，你可以对比着看。
Java 版本的写法：
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(); ans.add(Arrays.asList(arr[i - 1], arr[i])); } else if (diff == minDiff) { ans.add(Arrays.asList(arr[i - 1], arr[i])); } } return ans; } }Python 版本：
from typing import List class Solution: def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]: arr.sort() ans = [] min_diff = float("inf") for i in range(1, len(arr)): diff = arr[i] - arr[i - 1] if diff < min_diff: min_diff = diff ans = [] if diff == min_diff: ans.append([arr[i - 1], arr[i]]) return ans注意 Python 版本里我用了arr.sort()而不是sorted(arr)，区别在于前者原地排序，不产生新列表，能省一点内存。另外min_diff初始值用了float("inf")，而不是10**6或者别的魔法数，这样即使数组里全是极端大数也不会出错。
3.2 这些细节最容易踩坑
第一处：diff < minDiff时，清空之后一定要把当前对加进去。我第一次写这个版本时，以为清空后再循环到下一个i就自然会加入，结果发现当前这对被漏掉了。正确逻辑是clear之后立刻push_back，缺一不可。
第二处：比较符号的选择。有人会把diff < minDiff写成diff <= minDiff，然后就不用else if了。这种写法有问题吗？问题很大。如果diff == minDiff时走的是第一个分支，那每次相等都会clear，结果就是所有等于最小差的对全部被清掉，最终只剩最后一对，输出不完整。所以第一次写这种状态机时，建议老老实实用if / else if把“小于”和“等于”分开处理，想清楚再合并。
第三处：排序后差值为负数的问题。我见过有人担心数组里有负数，arr[i] - arr[i - 1]会不会是负的。不会。排序保证arr[i - 1] <= arr[i]，所以差值永远是>= 0的。事实上，在排序数组里求差值的时候直接用减法就够了，完全不需要调用abs，用abs反而会掩盖掉“这一对是否真的有序”的信息。
第四处：数据类型的选用。元素范围是-10^6到10^6，相邻差最大也就2 * 10^6，用int完全够，不需要long，更不需要double。用double还会带来浮点数比较的潜在风险，虽然这道题差值一定是整数，但养成“整数问题用整型”的习惯总没错。
第五处：对INT_MAX/MAX_VALUE的初始值不要偷懒。有些人为了省事，把minDiff初始化成一个很大的数比如10**9，这在本题也能过，但遇到更严格的数据范围时可能翻车。直接用语言自带的INT_MAX/Integer.MAX_VALUE/float("inf")是最稳的。
3.3 复杂度分析与边界情况
时间复杂度就是排序加的线性扫描：O(n log n)。空间复杂度取决于排序算法的实现，主流语言的库排序一般是O(log n)到O(n)的辅助空间，题目通常不卡这个。
边界情况其实很简单，因为题目保证了len >= 2，所以不用做空数组处理。如果面试官问“要是长度小于 2 怎么办”，你就说那可以直接返回空列表，因为不存在任何数对。另外由于元素互不相同，你也不用考虑“差值为 0 的重复元素对”，这让代码能干净地处理所有情况。万一题目改成允许重复元素，那最小差会变成 0，所有相同元素的组合都要收集，复杂度会高一个量级，这个扩展点在后面会讲到。
4. 同类题对比与难度升级
4.1 和“最小差值”系列摆在一起看
LeetCode 里名字带“最小差值”的题不少，但它们考的其实是完全不同的思路，放在一起对比比单刷一道题收获大得多。
- LeetCode 908（最小差值 I）：给每个元素
nums[i]都可以在[nums[i] - k, nums[i] + k]范围内变化，问数组最大值与最小值之间可能的最小差。这题不排序也行，本质就是看当前最大值和最小值能不能通过调整靠在一起，复杂度O(n)，脑筋急转弯的成分更多。 - LeetCode 910（最小差值 II）：给每个元素要么加
k要么减k，要最小化更新后数组的极差。这道题就得排序了，然后枚举“从哪里切开：左边都加k，右边都减k”，同时还要考虑负数翻正的情况，复杂度O(n log n)，比 1200 难一档。 - LeetCode 1984（学生分数的最小差值）：从一个数组里选
k个元素，让这k个元素中最大值减最小值尽可能小。解法是排序后滑动窗口，固定长度为k的窗口内首尾相减取最小。它和 1200 的关系很直接：1200 相当于k = 2时的 1984，只不过 1984 要输出最小值本身，而 1200 要输出所有数对。
把这些题放在一起就会发现一个规律：凡是“求某种相邻/窗口内的最小落差”的题，排序往往是第一步，然后要么直接扫描相邻元素，要么套一个固定长度的滑动窗口。这个套路比背某一道题的代码管用得多。
4.2 如果题目改成这些变体，怎么应对
变体一：数组里有重复元素，要求返回所有差值为 0 的数对。这时最小绝对差变成了 0，你需要把原数组按值分组，每个值出现次数大于 1 时，两两组合都是答案。注意如果某个值出现 3 次，那就有C(3,2) = 3对，输出量级可能很大，光构造答案就是O(n^2)级别，已经不能只看算法复杂度了。
变体二：不返回数对，只返回最小差的值。这题就更简单了，排序后扫一遍相邻差取最小就行，甚至可以在排序后通过“求相邻间隙最小值”解决，连结果集都用不上。
变体三：要求返回数对在原数组中的下标，而不是值本身。那就需要一个“值 + 下标”的结构体一起排序，最后把匹配到最小差的下标对输出。这个变体在真实工程项目中很常见，因为很多时候你需要定位元素位置而不是只关心值。
变体四：把数组改成二维点集，求最近点对距离。这是另一个经典问题，简单的一维排序法就不够用了，需要分治或者扫描线，复杂度是O(n log n)。从 1200 到最近点对，是一条很自然的知识升级路线，有精力的同学可以顺路看看。
5. 常见问题与排查技巧实录
5.1 刷题时最常遇到的三种卡壳情况
先说第一种：只输出第一对或者漏掉最后一对。原因基本就是 3.2 节里说的那个状态机问题——diff < minDiff后清空了ans但忘了把当前对加进去。我自己就栽过这个跟头，后来养成了一个习惯：凡是看到“更新最值 + 重建结果集”这种逻辑，写完代码先心里默念三个分支走一遍，再提交。
第二种：结果对顺序不对。比如输出[[2,3],[1,2]]，这是因为你在扫描完所有相邻对之后又做了额外的排序，或者你把原数组排序后又改变了数组本身的顺序，导致后面拿到的是混乱的序列。其实只要保证两点就能避免：排序数组后从左往右扫描，找到的每一对都是升序；外层结果集的顺序天然就是按数对首元素升序排列的。如果你用了set或者map来收集结果，反而可能破坏顺序，这点要特别注意。
第三种：用abs判断导致逻辑绕来绕去。有些人没有排序就直接暴力，还试图用abs去判断差值，最后发现要么超时，要么结果重复。正确的姿势始终是：先排序，再说相邻。如果你站在abs的角度去思考这道题，基本上已经跑偏了。
5.2 面试现场怎么把这道题答出层次
如果面试官让你现场写这道题，我建议你按这个节奏来：第一步，先抛暴力解，告诉面试官复杂度是O(n^2)，数据量大时不可行；第二步，抛出排序的思路，同时把“为什么只看相邻对”的反证法讲清楚；第三步，写代码时选择一次扫描的版本，边写边解释diff < minDiff和diff == minDiff两个分支的用途。做完这三步，这道题基本就能拿到不错的评价。
如果面试官继续追问能不能更快，你可以提一下基数排序或计数排序的扩展思路。考虑到元素范围是-10^6到10^6，跨度只有2 * 10^6 + 1，完全可以直接开一个大数组做计数排序，然后线性扫描所有非空桶的相邻间隔。这样复杂度可以降到O(n + range)，其中range = 2 * 10^6 + 1，在这个题里其实完全可行。虽然 LeetCode 官方并不要求这样做，但能说出这个思路说明你理解“排序”和“桶”之间的关系，而不只是背了一个sort()。
另外，如果你刷题时关注过 LeetCode 周赛，最近几期周赛频繁出现“基于排序后相邻关系做区间合并”的题，比如周赛 430 的一些问题，核心思路跟 1200 是一脉相承的。热门 100 题里像073 爱吃香蕉的狒狒那种二分查找题，是另一种“先想清楚单调性再二分”的套路，和 1200 的“先排序再扫描”刚好互为补充。刷题不能只盯着一道题的代码，要能把同一类思路串起来，这样遇到新题才不会慌。
5.3 一个适用于所有“相邻差”题目的调试技巧
最后分享一个小技巧。如果你在写这种“遍历相邻元素并维护最值”的题目时总出 bug，可以在本地把数组改成[5, 1, 4, 2, 3]这种故意打乱顺序的手工测试用例，然后打印出排序后的数组、每一对相邻差值、每一步更新后的minDiff和ans。你会很直观地看到“全局最小值是怎么被一步步发现的，结果集又是怎么被清掉重建的”。这个调试方法不只在 1200 有用，遇到任何类似“求最小区间 / 最小差值”的题都能帮你快速定位问题。
我自己在实际刷题中还有一个体会：这道题虽然简单，但每过一段时间重写一遍，都会有新的感悟。第一次可能是照着题解抄的，第二次能自己推导出相邻性结论，第三次能写出一次扫描的版本，第四次就能在面试里流畅地把扩展思路也讲出来了。LeetCode 1200 不是一个值得炫耀的难题，却是一个值得反复咀嚼的基础题——把它的原理吃透，后面遇到再难的“排序 + 相邻性”问题，你都有底气说一句“这题我熟”。
