1877. 数组中最大数对和的最小值这个编号在 2026.1.24 的每日题单里非常显眼。光是标题里数组最大数对和最小值三个词叠在一起就足够劝退一批刚刷题的人但它其实是一道非常典型的贪心排序题。真正值得花时间研究的不是那几行代码而是为什么排序后首尾配对就是最优解这件事。这篇文章从题面拆解开始讲清楚贪心证明、多语言实现、复杂度边界再延伸到实际工作里的配对均衡场景。无论你是刚接触算法题的新手还是想在面试里把理由讲明白的求职者这条拆解路径都值得完整走一遍。1. 题目到底在问什么先把最大数对和翻译成人话1.1 题面重新拆解LeetCode 1877 的原始描述并不复杂给你一个长度为偶数的数组nums把它分成n/2个数对每个数对里的两个数相加得到数对和。一组配对方案里最大的那个数对和叫做最大数对和。题目要求你调整配对方式让这个最大值尽可能小最后返回这个最小值。很多人第一次看会卡在最小化最大值这句话上。它不是一个求某个数字最小值的简单问题而是一个在大量配对方案里做决策的问题。数组长度最多到 10^5如果真去枚举所有配对方案那是(n-1)!!级别的爆炸组合所以必须找规律。而这类分组配对 优化全局指标的问题十有八九会往排序和贪心方向想。要注意的是题目名字里带数组但和区间、滑动窗口、树状数组这些数据结构没有关系。它不要求动态维护某个窗口的最小值也没有单点更新和区间求和的操作。它的核心其实是一个数学配对模型数组只是承载数据的容器。1.2 一个例子看懂最小值的含义拿示例来说nums [3,5,2,3]三个对象其实数组长度是 4所以要拆成 2 个数对。如果随便配对成(3,5)和(2,3)数对和分别是 8 和 5最大数对和是 8。但这不是最好的方案。换一种配对(3,3)和(2,5)数对和分别是 6 和 7最大数对和是 7比 8 小。所以答案是 7。第二个示例[3,5,4,2,4,6]排序后是[2,3,4,4,5,6]首尾配对得到(2,6)8、(3,5)8、(4,4)8最大数对和是 8。这个过程中最关键的点是为了让最大值变小不能让两个较大的数字凑在一对里。把大数字和小数字互相稀释峰值就会降下来。数组随意配对最大数对和优化后配对最大数对和[3,5,2,3](3,5), (2,3)8(3,3), (2,5)7[3,5,4,2,4,6]任意顺序可能大于8(2,6), (3,5), (4,4)81.3 数据约束给我们的提示题目约束里数组长度是偶数n 10^5元素值在[1, 10^5]范围内。这意味着两件事O(n^2)的暴力解法一定超时必须把复杂度降到O(n log n)或更低。数值都是正数这让很多初始化方式可以简化但写代码时仍然要养成更严谨的习惯后面会专门提到。这个约束本身就是信号看到 10^5先想排序。排序的O(n log n)在绝大多数在线评测系统里都能接受配合一轮线性扫描整体效率非常稳。2. 为什么排序后首尾配对就是最优解2.1 最自然的直觉让大数和小数互相压住先看一个直观感受。如果数组排序成[a1, a2, ..., an]最大值an是无论如何都躲不掉的它必须出现在某个数对里。如果让它和次大值a(n-1)配对那么这一对的数对和会接近2 * 最大值很可能直接把整体峰值拉得很高。反过来如果让an去和最小值a1配对虽然这一对的和不一定小但至少不会出现两个大数叠加的极端峰值。更进一步的思考是配对方案其实可以看作是从数组两端往中间走左指针从最小的数出发右指针从最大的数出发每次取两端各一个组成一对。这样整体上的数对和会比较均匀不会出现一个数对很大、另一个数对很小的失衡状态。这种两端配对的思路也叫排序 双指针是算法题里非常高频的组合套路。2.2 数学上给一个下界证明直觉只是起点面试时更要能讲清楚为什么这样最优。这里给一个简洁的交换论证。把数组排序成a1 a2 ... an。先看最小元素a1和最大元素an。在任意配对方案里a1一定和一个元素x配对an一定和一个元素y配对。如果说这两种配对恰好不是(a1, an)那么当前方案里有这样两对(a1, x)和(y, an)这时我们把它们重新组合成(a1, an)和(x, y)比较两种组合的最大数对和。原来的最大值至少是max(a1 x, y an)重组后的最大值是max(a1 an, x y)。因为排序保证a1 y所以a1 an y an又因为x an所以x y y an。也就是说重组后的两个数对和都不超过原来那个y an整体的最大数对和不会变大。这说明如果最优方案里最小值和最大值没有配对那我可以把它俩强制配对同时不损害结果。所以一定存在一个最优方案让a1和an在一起。把这一对拿掉剩下的数组仍然是有序的偶数长度数组对[a2, a3, ..., a(n-1)]重复同样的论证最后得到的配对方式就是排序后从两端依次配对。这就是完整的贪心证明比显然成立四个字有说服力得多。2.3 常见错误方案相邻配对为什么不对很多人容易想到排序后把相邻元素两两配对也就是(a1, a2)、(a3, a4)这样。这个思路在 LeetCode 561 数组拆分 I 里是正确答案因为那题要的是让每对的最小值之和最大。但在这题里相邻配对会带来灾难性后果。用一个反例[1, 2, 100, 101]。相邻配对(1,2)和(100,101)数对和是 3 和 201最大数对和是 201。首尾配对(1,101)和(2,100)数对和是 102 和 102最大数对和是 102。差距一目了然。相邻配对把 100 和 101 这两个大数放到了一起直接制造出巨大的峰值。这正好验证了前面的直觉两个大数必须被两个小数隔开不能抱团。所以积累过 561 的解法后看到 1877 时反而要提醒自己同样是排序优化目标不同配对方式就完全不同不能套模板。3. 代码实现与运行细节3.1 Python 实现Python 的写法非常短核心就是排序加双指针。from typing import List class Solution: def minPairSum(self, nums: List[int]) - int: nums.sort() ans 0 left, right 0, len(nums) - 1 while left right: ans max(ans, nums[left] nums[right]) left 1 right - 1 return ansnums.sort()是原地排序不额外占用新的数组。left从最小值出发right从最大值出发每轮组成一对后同时向中间移动。ans维护所有数对和的最大值。这里有个小细节ans初始化为 0。因为题目数据都是正数所以这样写没问题。但如果放到一个通用场景数组里可能有负数那ans 0就会出现严重错误。比如[-5, -2, 1, 3]排序后首尾配对是(-5,3)和(-2,1)和分别是-2和-1最大数对和是-1但ans 0会让函数错误返回 0。更稳的初始化方式是直接用第一对数对和来赋值ans nums[left] nums[right]然后在循环里不断更新。虽然 LeetCode 本题不会踩坑但这种习惯能帮你少出很多生产环境里的 bug。3.2 Java 实现和 JavaScript 排序的坑Java 写法同样简单import java.util.Arrays; class Solution { public int minPairSum(int[] nums) { Arrays.sort(nums); int ans 0; int left 0, right nums.length - 1; while (left right) { ans Math.max(ans, nums[left] nums[right]); left; right--; } return ans; } }JavaScript 里最需要注意的是sort()的默认行为。nums.sort()默认把元素转成字符串再按字典序排序所以[10, 9]会被排成[10, 9]而不是[9, 10]。正确的写法必须传入比较函数var minPairSum function (nums) { nums.sort((a, b) a - b); let ans 0; let left 0, right nums.length - 1; while (left right) { ans Math.max(ans, nums[left] nums[right]); left; right--; } return ans; };这个坑几乎是前端算法面试的必问点。一旦遗漏比较函数整个排序结果就是错的后面的双指针也无从谈起。C 的写法则是sort(nums.begin(), nums.end())然后同样的双指针。语言不同核心思路完全一样。3.3 复杂度分析时间复杂度排序O(n log n)双指针扫描O(n)整体是O(n log n)。空间复杂度除了排序内部可能使用的栈空间双指针本身只占用常数空间所以是O(log n)或O(1)取决于排序实现。这个复杂度对面 10^5 的数据规模没有任何压力即使再加几倍数据也能跑完。3.4 边界条件实战几个容易忽略的边界场景数组长度是 2排序后直接进入一次循环left 0right 1循环体执行一次后 left 和 right 相遇返回两数之和。逻辑天然成立。数组全部是同一个数比如[5,5,5,5]任何配对结果都是 10首尾配对也会得到 10不会出错。数组已经是降序排序就是干这个用的不需要手动维护原顺序。如果题目允许负数或者 0答案初始化方式要改成首对数对和这个前面已经说过。还有一个小提醒不要为了图省事把len(nums)反复写在循环条件里Python 里虽然开销不大但每次循环都重复计算总归不够优雅。更好的做法是像示例代码那样先用一个变量right len(nums) - 1固定下来。4. 这道题的影响范围从数组配对到实际调度4.1 抽象成一个通用模型很多数组题看似只在虚拟的评测环境里出现实际背后的模型非常通用。把 1877 抽象出来就是一句话有 2m 个任务每个任务有一个已知的重量现在要把它们两两分到 m 个容器里希望最重的那个容器尽量轻。这个模型在真实场景里到处都是。举个例子之前我参与过一个内部系统改造有一批接口耗时数据需要把这些接口两两组合部署到同一台机器上目标是最慢的机器不要成为瓶颈。这就是一个典型的最小化最大数对和问题接口耗时是数组元素机器是最数对组最大数对和就是最慢机器的耗时。再比如资源分配中的主备配对A 类资源和 B 类资源互相搭配不希望某一对资源占用特别高。把耗时、负载、成本这些指标量化成数组元素1877 的解法就可以直接套用。当然真实系统里往往还有容量上限、依赖关系、地域分布等额外约束不能把 1877 的答案当成终极方案。但用它来快速生成一个初始配对方案再在局部做微调效率会非常高。4.2 和相似题目的关系对照刷题量上去之后会发现很多题的长相接近但目标函数完全不同。整理一个对照表题号 / 场景典型目标与 1877 的关系561. 数组拆分 I排序后相邻配对让每对较小值之和最大同为排序配对但优化目标不同解法也不同881. 救生艇排序后双指针让船的数量最少双指针思路相同但有重量上限约束167. 两数之和 II有序数组双指针找目标值提供双指针基础操作1877 的双指针是它的变种259. 三数之和小于目标值排序后双指针计数同样利用有序性缩小搜索范围948. 令牌放置排序后双指针尽量增加分数贪心方向不一样但排序预处理是同一个套路做这类横向对比比单纯刷完一道题收获更大。你会发现很多问题都可以拆成排序 双指针 目标函数三段式区别只在于目标函数是求最大、最小、计数还是别的。4.3 为什么刷题时要关注这类最小化最大值思路最小化最大值是算法题里一个经典大类。常见做法是二分答案加贪心验证但这题比较特殊它不需要二分因为贪心策略本身就能直接达到最优值。关注这类题的价值在于它能训练你把决策问题转化为排序后配对的直觉。很多候选人写 1877 都能写出正确代码但被追问为什么不是相邻配对时就支支吾吾。这恰恰说明他只是在背模板没有真正理解目标函数对配对结构的影响。如果你能在一道中等题上把证明讲清楚面试官通常会认为你在遇到没有见过的变体时也能通过推理找到解法。这种推理能力才是算法面试真正想考察的东西。5. 刷题验证与面试避坑指南5.1 用暴力枚举做验证开发过程中一个非常实用的习惯是写一个暴力枚举程序专门用来验证贪心解法的正确性。尤其对配对类问题小数组规模下枚举所有配对是可行的。from math import inf def brute_min_pair_sum(nums): n len(nums) used [False] * n best inf def dfs(cur_max): nonlocal best i 0 while i n and used[i]: i 1 if i n: best min(best, cur_max) return used[i] True for j in range(i 1, n): if not used[j]: used[j] True dfs(max(cur_max, nums[i] nums[j])) used[j] False used[i] False dfs(-inf) return best这个暴力的时间复杂度是指数级只能在n 10时使用。你可以随机生成若干小数组把brute_min_pair_sum的结果和minPairSum的结果放在一起比对。多跑几轮随机测试如果全部一致代码的正确性就有了非常硬的保障。我写这个暴力脚本时特意用了一个小技巧固定先找第一个未配对的元素再为它选择配对对象。这样不会重复枚举同一套配对方案效率会比全排列高不少也更容易写对。5.2 易错点排查总结一下我实际写题时遇到过的坑忘记排序没有排序就双指针结果完全是乱的。排序是这套解法的地基。JavaScript 里漏写sort的比较函数[10, 9]这种数据会直接翻车而且是在样例少的时候很难发现的那种翻车。答案初始化不当默认0在负数场景下会错误。更通用的写法是用第一对的和初始化。索引边界写错如果写成nums[i] nums[n - i]当i 0时会出现nums[n]越界。正确写法是nums[left] nums[right]或者nums[i] nums[n - 1 - i]。额外拷贝数组有些同学为了不改变原数组先复制一份再排序。这个操作没问题但如果只是想做题完全没有必要。原地排序足够除非你后面还要用原数组的顺序。返回值类型不清LeetCode 这题答案不会超过 2 * 10^5int足够。但如果把元素范围放大到 10^9就要改成long。写任何项目代码时多想一步数据上限总没有坏处。5.3 面试时可以怎么讲如果面试中遇到这道题建议按这个顺序来先说结论先把数组排序然后用双指针从两端向中间配对记录每次配对的最大值。用一个反例解释为什么相邻配对不行[1,2,100,101]相邻配对最大和是 201首尾配对最大和是 102。给出交换论证最小数一定要和最大数配对否则交换后最大数对和不会变大。最后写代码。不要一上来就写代码。面试官更想看到的是你如何从问题推导出算法。尤其是交换论证这一步它是区分真正理解此题和死记硬背此题的分水岭。5.4 一点实操心得这道题最让我意外的是它居然真的能直接用在线上环境的资源分配里。当时我面对一组服务耗时数据用 1877 的排序双指针生成配对结果十分钟就写完了核心逻辑上线后的效果也很接近预期。虽然真实系统后来加了机房、可用区等限制但最初的极简版本已经给了我一个足够好的基线。根据自己的经验面对最小化最大值类问题不要一上来就套二分。先问自己一句排序加贪心能不能直接得到最优解如果能像 1877 这样找到一个简单的证明路径代码往往比二分方案更短也更容易维护。如果找不到证明再退一步考虑二分答案加检查函数。这条路线能覆盖大多数同类问题也是我刷题时最常用的思考方式。