如果你在 LeetCode 上刷到第 1877 题大概率会看到题解区一句轻飘飘的话把数组排序最小的跟最大的配成一对次小的跟次大的配成一对所有数对和里取最大值就是答案。我第一次看到这个解法时愣了一下就这么简单然后自己写了个暴力分组想验证发现 n 稍微大一点就根本跑不完。这篇文章我就来把这道“数组中最大数对和的最小值”完整拆开讲清楚题目到底在问什么、排序解法凭什么正确、代码怎么写不踩坑以及怎么从这一道题里提炼出一类排序贪心题的通用题感。适合刚入门算法刷题、想搞懂贪心证明、或者面试前快速过一遍高频题的读者。1. 先把题目翻译成人话它到底在问什么1.1 两个约束和一个目标原题描述不长但第一次读容易绕。给你一个长度为偶数 n 的数组 nums要求把所有元素两两分组每个元素必须恰好出现在一个数对里不能多用也不能漏用。对于每一对数把两个元素加在一起得到一个“数对和”。最后所有数对和里必然有一个最大值题目要的是在所有的分组方式中让这个最大值尽可能小。举个例子就清楚了。nums [3,5,2,3]n 4需要分成两对。分组方式有两种(3,5) 和 (2,3)数对和分别是 8 和 5最大值是 8(3,3) 和 (5,2)数对和分别是 6 和 7最大值是 7。所以答案是 7。注意这里不是让“数对和的总和最小”而是让“最重的那一对尽量轻”。很多初学者在这里理解偏掉后面怎么想都不对。1.2 暴力拆分到底有多慢如果不排序、不贪心直接枚举全部分组方案能算出来吗n 个元素分成 n/2 个无序数对的方案数是 (n-1)!!也就是 (n-1) 乘以 (n-3) 乘以 (n-5) 一直乘到 1。n 10 的时候是 945 种n 12 是 10395 种n 14 已经到 135135 种。这个数增长极快而题目里 n 的上限是 10^5所以暴力枚举在数学上就判了死刑。这是典型的“看着像组合问题实际上有简洁规律”的题型。遇到这种题第一反应应该是找结构而不是硬枚举。1.3 为什么不用二分答案也能做“最大值最小”这个表述在很多题里对应的套路是二分答案猜一个上界 m检查是否存在某种分组让所有数对和都不超过 m然后不断收紧 m。这题当然也能这么做check 的过程还是离不开排序加双指针。但仔细想想由于题目要求把全部元素恰好配完且目标是最小化那个上界我们其实可以直接构造出最优分组连二分的 log 都不用多花。换句话说这题的最优解不是靠“猜答案”得来的而是靠“直接证明某种配对必然最优”得到的。明白这一点你就知道为什么题解区只要一句“排序后首尾配对”就够了——因为剩下的工作全是证明这个配对为什么对。2. 为什么最大值必须和最小值绑在一起贪心论证2.1 直觉解释先说个生活化的类比。想象你要把一群体重差距很大的人两两分组坐跷跷板每组的“总重量”是一个数对和你要让最沉的组尽量轻。最重的那个胖子不管跟谁坐整组重量都小不了所以必须给他配一个最轻的人来“压舱”。最轻的人跟谁坐都轻让他去吸收最重的人是最划算的安排。这就是首尾配对的直觉大数配小数互相平衡避免出现两个“巨无霸组合”。反过来想如果你把最大的数和第二大的数放一起这一组直接爆炸而最小的数和第二小的数放一起虽然这一组很轻但整体最大值已经被刚才那组拉高了没有任何收益。这就是“局部很优全局很亏”的典型。2.2 交换论证一步一步证明贪心成立直觉只能帮我们猜答案要确认答案还得给证明。排序贪心题的经典证明方法是交换论证我完整写一遍你以后遇到类似的题可以直接套这个思路。设排序后的数组为 a0 ≤ a1 ≤ ... ≤ a_{n-1}。假设存在某个最优分组方案其中最大的元素 a_{n-1} 没有和最小的元素 a0 配对而是和某个 ai 配对0 i n - 1同时 a0 和某个 aj 配对0 j n - 1j ≠ i。这两对的数对和分别是s1 a_{n-1} ais2 a0 aj现在强行交换让 a_{n-1} 和 a0 配对ai 和 aj 配对。交换后的两对和是s1 a_{n-1} a0s2 ai aj关键来了。因为 a0 ≤ ai所以 s1 ≤ a_{n-1} ai s1。又因为 aj ≤ a_{n-1}排序后数组中除了 a0 和 a_{n-1} 之外的元素都不可能比 a_{n-1} 大所以 s2 ai aj ≤ ai a_{n-1} s1。因此交换后两个新数对的和都不超过原来两个数对和中的较大者整体最大数对和不可能变大。这意味着只要有一个最优方案没让最大值和最小值配对我们就能通过交换把它改成让最大值和最小值配对同时不破坏最优性。把这两个元素从数组里拿掉剩下的 n - 2 个元素继续用同样的论证。反复套用最后一定能得到一个首尾配对的最优方案。这个证明不依赖元素是否为正、是否重复所以适用范围很广。2.3 一组反例破除错误直觉很多人会直觉地认为“把大的跟大的放一起另一对小的跟小的放一起最大数对和可能更小啊。”用 [1,2,8,9] 算一笔账就清楚了。排序后还是 [1,2,8,9]三种典型分组分组方式数对和最大数对和(1,9), (2,8)10, 1010(1,2), (8,9)3, 1717(1,8), (2,9)9, 1111首尾配对的最大值是 10相邻配对是 17混合配对是 11。原因正如前面所说把大数集中在一起单个数对和就失控了只有让大数去“吸收”小数才能把最重的组压下来。这个例子也说明排序是首尾配对的前提——不排序直接取原数组首尾那个“首”未必是最小值“尾”未必是最大值配对就失去了意义。3. 代码实现从一行版到双指针版3.1 Python推荐写法和生成器写法理解了证明代码就非常简单了。最稳妥的 Python 写法是这样from typing import List class Solution: def minPairSum(self, nums: List[int]) - int: nums.sort() ans 0 n len(nums) for i in range(n // 2): ans max(ans, nums[i] nums[n - 1 - i]) return ans先对 nums 原地排序然后从两端向中间走。nums[i] 是从小到大的一端nums[n - 1 - i] 是从大到小的一端两者配对取所有配对和的最大值。这里我用的是 nums.sort() 而不是 sorted(nums)因为题目没有要求保留原数组原地排序省掉一份额外的 O(n) 空间。有些人喜欢写成一行class Solution: def minPairSum(self, nums: List[int]) - int: nums.sort() return max(nums[i] nums[~i] for i in range(len(nums) // 2))这里 ~i 表示 -i - 1也就是从数组尾部往前的第 i 个位置。这么写很简洁但 ~ 运算符对不熟悉位运算的读者来说可读性较差。我个人建议在工程代码或者面试里写显式的 n - 1 - i意思一目了然。3.2 用双指针理解“从两端向中间逼近”除了用索引计算还可以用双指针逻辑上更直观class Solution: def minPairSum(self, nums: List[int]) - int: nums.sort() left, right 0, len(nums) - 1 ans 0 while left right: ans max(ans, nums[left] nums[right]) left 1 right - 1 return ansleft 从最小的元素开始right 从最大的元素开始每配对完一对就往中间移动一步。这个版本的好处是它把“首尾配对”这件事的物理过程直接写进了代码里读起来不需要在脑子里换算索引。我刷题时遇到类似的排序贪心题也习惯先写双指针版本因为它最能体现贪心策略的实际执行方式。3.3 C 和 Java 的写法C 实现同样直接主要注意 sort 的范围class Solution { public: int minPairSum(vectorint nums) { sort(nums.begin(), nums.end()); int n nums.size(); int ans 0; for (int i 0; i n / 2; i) { ans max(ans, nums[i] nums[n - 1 - i]); } return ans; } };Java 版本就是 Arrays.sort 加一层循环class Solution { public int minPairSum(int[] nums) { Arrays.sort(nums); int n nums.length; int ans 0; for (int i 0; i n / 2; i) { ans Math.max(ans, nums[i] nums[n - 1 - i]); } return ans; } }三种语言的核心完全一致区别只在排序 API 的调用方式。这也是这类题的魅力思路想通之后翻译成任何语言都是十分钟的事。3.4 复杂度分析为什么总共只有 O(n log n)整个算法就两步排序和线性扫描。排序的时间复杂度是 O(n log n)归并排序、快速排序、堆排序都是这个量级配对的循环只走了 n/2 次时间复杂度是 O(n)。两者相加总时间复杂度就是 O(n log n)空间复杂度是 O(1)这里说的是原地排序的情况nums.sort()不会创建新数组。如果使用 sorted(nums)排序后原数组还在但生成新列表需要 O(n) 的额外空间。在 LeetCode 上这样写通常也不会超时但面试官如果追问空间复杂度你要能说清楚这两种写法的差别。我个人的习惯是除非题目明确要求不修改入参否则一律原地排序。4. 边界情况和实战中容易踩的坑4.1 最小规模输入n 2当数组只有两个元素时只有一种分组方式答案就是两个数之和。代码里 range(n // 2) 只循环一次正好覆盖这种情况。这个边界太简单一般不设卡但别忘了它。还有个容易忽略的点题目保证 n 是偶数所以 n // 2 永远整除。如果面试官出了一个变体题数组长度是奇数怎么办这时候要先问清楚规则是允许丢弃一个元素还是允许有一个三个元素的组不同规则下的贪心策略完全不同直接套 n // 2 就会漏掉一个元素答案必错。4.2 负数和重复元素证明里没用到非负性原题的 nums[i] 是正整数但首尾配对这个结论对负数同样成立。你可以用 [-7, -1, 2, 4] 验证一下排序后 [-7, -1, 2, 4]首尾配对得到 (-7,4) -3 和 (-1,2) 1最大值是 1。其他分组方式可以分别算一下(-7,2) -5 和 (-1,4) 3 最大值是 3(-7,-1) -8 和 (2,4) 6 最大值是 6。首尾配对依然最优。原因在于交换论证里只用了排序的单调性没有假设元素必须为正。重复元素更不用怕。数组里多个相同的最大值时谁去跟最小值配对结果都一样排序后系统自动把它们放到数组末尾首尾配对会自然地把它们分配到不同的组里整个过程不需要额外处理。4.3 索引、切片和副本的隐蔽坑代码主体越简单越要注意细节。我复盘过自己犯过的错最典型的几个循环写成 range(n) 而不是 range(n // 2)。这样会把已经配对的元素再次配对得到的结果会错误地偏大或偏小。索引写错。正确写法是 nums[n - 1 - i]新手容易写成 nums[n - i]数组下标会越界Python 会给你一个 IndexErrorC 则直接是未定义行为。使用切片产生副本。比如有人写sorted_nums sorted(nums)后又对 sorted_nums 做切片 [:n//2] 和 [n//2:] 再配对每一步都创建新列表额外空间累加到 O(n) 甚至更多。在这个题目里完全没有必要。在循环里反复调用 sorted(nums)。排序一次就够循环里每次调用都是 O(n log n)直接把复杂度拖垮。C 中 int 是否溢出。原题约束很小两个 nums[i] 加起来不过 2×10^5int 完全放得下。但如果你在做其他平台的变体题数值范围放大到 10^9两数和会逼近 2^31那时候建议直接用 long long 存 ans求稳不亏。5. 题感培养如何识别一类“排序贪心”题5.1 这类题长什么样刷多了你会发现很多数组配对的题都有三个共同特征数组要全部用上、元素要成对组合、优化目标是某个关于数对和的统计量。只要看到“最大...的最小值”或“最小...的最大值”这类表述同时又有“每个元素只能用一次”的约束我第一个会想到排序加贪心而不是动规。为什么因为排序能把数组变成一个有序序列而有序序列里“最大”和“最小”这两个极端元素的位置就很明确我们只需要决定极端元素怎么配对中间元素的配对可以递归考虑。这就是 1877 的核心解题路径。5.2 和 561、881 对比同样是排序配对方式却不同有几个经典题经常放在一起对比能帮你把这类题的脉络梳理清楚。我整理了一张表题目目标排序后配对方式理解1877 最大数对和的最小值最小化最大数对和首尾配对大数必须配小数来压平衡881 救生艇最小化船数最重的人配最轻的人尽量把重的人“塞进”已有船省船561 数组拆分最大化每对较小值之和相邻配对让更多大数有机会成为一对中的较小值561 是最容易和 1877 混淆的。它要求把数组分成若干对每对取较小值然后让这些较小值的总和最大。排序后如果也做首尾配对比如 [1,2,3,4] 配成 (1,4) 和 (2,3)较小值是 1 和 2总和只有 3如果相邻配对成 (1,2) 和 (3,4)较小值是 1 和 3总和是 4。原因是 561 的目标函数是“所有较小值加起来”每配对一次就有一个较大的数被“作废”作废了就不参与总和所以应该让较大的数两两相邻减少被作废的大数数量。而 1877 的目标是压住单个最大值不存在“作废”这个概念反而要让大数去配小数来压低峰值。记住这个区别就够了目标函数是“加总贡献”的多半相邻配对目标是“压住单个峰值”的多半首尾配对。881 救生艇是另一个变体它有限重约束但核心贪心依然是最重的人先考虑能配最轻的就配配不了就单独走。5.3 面试时怎么答这道题如果面试官考这道题我不建议上来就写代码。把思路讲清楚比手速更重要。推荐按三步走先说排序。这样可以得到全局有序性让极端元素的位置一目了然。再说配对策略。最小的和最大的配对次小的和次大的配对直到中间相遇。最后补一句证明。用交换论证说明如果最大值没和最小值配对交换后最大数对和不会变大反复交换得到首尾配对方案最优。这三句话说清楚面试官基本就会点头。代码反而是最后一步几分钟就能写完。很多人面试时栽在这道题上不是不会写排序而是说不清“为什么这样配”所以证明那块一定要提前练熟。最后分享一点我自己的刷题体会。这类题最容易犯的错不是代码写错而是把简单问题想复杂——一看到“最小化最大值”就冲上去写二分、写动态规划。实际上成对分组加极值优化这个组合里排序加双指针是最常见也最好用的突破口。1877 这道题算是把这条路完整走了一遍读题、怀疑、证明、写码、看边界每一步都不难但串起来就是一套可复用的贪心解题流程。你下次再遇到类似的表述先停下来问自己一句如果把数组排好序当前的最值元素和谁配最合理想通了代码基本就是十分钟的事。