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[i1]。由于a[i] a[i1] a[j]所以a[i1] - 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^45 千万次计算也很悬。所以这道题的第一课是看到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: vectorvectorint minimumAbsDifference(vectorint arr) { sort(arr.begin(), arr.end()); vectorvectorint 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 diffdiff minDiff又找到一对和当前最小差值相等的直接追加进ansdiff minDiff这个差值太大什么也不用做。这样一轮走完ans里自然就是所有最小差值的相邻对。这就是下面这版一次扫描的实现也是我最推荐的写法因为它把“候选最小值的更新”和“结果集的重建”用同一个循环完成了代码更紧凑而且能直接看出你对这个状态机的理解。class Solution { public: vectorvectorint minimumAbsDifference(vectorint arr) { sort(arr.begin(), arr.end()); vectorvectorint 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 ListListInteger minimumAbsDifference(int[] arr) { Arrays.sort(arr); ListListInteger 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 不是一个值得炫耀的难题却是一个值得反复咀嚼的基础题——把它的原理吃透后面遇到再难的“排序 相邻性”问题你都有底气说一句“这题我熟”。