企业官网建设流程全解析

LeetCode 每日一题做到 1877，题目叫“数组中最大数对和的最小值”。我第一反应是这题八成要二分答案或者上动态规划，毕竟“最小化最大值”这个表述，放在力扣题库里十有八九会让人联想到二分模板。结果读完题发现，它其实是一道披着复杂外衣的贪心题，核心解法只有三步：排序、双指针、取最大值。这篇文章就把我怎么从读题到证明、再到用三种语言写出来的全过程拆开讲一遍，顺便说说这类题在面试里怎么快速识别套路。

这段内容适合两类读者：一类是在刷每日一题、想弄懂为什么贪心解法的同学，另一类是准备算法面试、需要在一分钟内给出方案和证明的候选人。先别急着往下翻答案，思考一个问题：给你nums = [3,5,2,3]，把四个数分成两对，每对求和，再取这两个和里较大的那个，你希望这个最大值尽量小，最优结果是多少？很多人会想到把3 和 5放一起、2 和 3放一起，得到8 和 5，答案是 8；但如果你改成3 和 3放一起、5 和 2放一起，得到6 和 7，答案是 7。后者明显更好。这个例子就是整道题的灵魂：要压的是“最大那个对”，而不是每个对本身的总和。

1. 把题目翻译成人话：到底要计算什么

1.1 题目条件与示例拆解

LeetCode 1877 的原文结构很简单：给你一个长度为偶数n的数组nums，你需要把数组里的元素两两配对，总共形成n/2个数对。每个数对的和称为“数对和”，现在要求你找到一种配对方式，让所有这些数对和的最大值尽量小，最后返回这个最小的最大值。注意，每个元素只能使用一次，而且所有元素都必须被配对，没有落单的。

拿nums = [3,5,2,3]来说，长度n=4，配对方式一共有三种：第一种(3,5)和(2,3)，数对和是8和5，最大值是8；第二种(3,2)和(5,3)，数对和是5和8，最大值还是8；第三种(3,3)和(5,2)，数对和是6和7，最大值是7。所以答案就是7。这个例子只要枚举一次就能理解题意，但真正的问题在于：当n到10^5时，配对方式是天文数字，必须找规律。

还有一个容易混淆的地方：题目不是要你“让所有数对和的总和最小”，也不是要你“让某一个固定的数对和最小”，而是要“保证最差的那一对也不太大”。这类问题在算法里叫“最小化最大值”，英文是minimize the maximum pair sum。一旦抓住了这个核心，你自然就会去思考：怎么分配才能让所有对都处在同一个比较低的水平上，而不是出现一个特别大的“短板”。

1.2 排序后相邻配对为什么是错的

很多第一次做这道题的人，包括我自己，想到的第一个朴素方案是：先排序，然后从左到右每两个相邻元素组成一对。比如排序后是[1,2,3,4,5,6]，相邻配对得到(1,2)=3、(3,4)=7、(5,6)=11，最大值是11。可这样真的最优吗？我们换成首尾配对：(1,6)=7、(2,5)=7、(3,4)=7，最大值是7，比11小得多。为什么相邻配对不行？因为排序之后，数值最大的几个元素会“集中”在数组尾部，如果它们两两配对，就会制造出一个巨大的和；而数组头部的小元素又非常小，它们和中等元素配对也是浪费。最优策略应当是把大数“拖住”，让每个小数去中和一个大数，让所有配对的和尽可能均衡。

从另一个角度看，如果数组里有且只有一个特别大的数，比如[1,2,3,4,5,100]，相邻配对是(1,2)=3、(3,4)=7、(5,100)=105，最大值被拉到了 105；但如果让1+100=101，再让剩下的2+5=7、3+4=7，最大值是101，虽然还是很大但已经压到了最低。因为 100 总要和某个数配对，和它配对的那个数越小，这对的和才越小，这就是“最小配最大”的直觉来源。

2. 贪心策略的完整证明：为什么必须“最小配最大”

2.1 关键引理：最大值必须和最小值配对

光有直觉不够，面试时如果只报出排序和双指针，很容易被追问一句：“为什么这样配对一定最优？”所以我们必须把证明写下来。先把数组排序，记为a[0] <= a[1] <= ... <= a[n-1]。我们把a[n-1]这个全局最大元素单独拎出来看：它一定要和数组中某个元素配对。设它的搭档是x，那么这一对的和就是a[n-1] + x。由于x一定是数组中的某个元素，而数组中的任意元素都不小于a[0]，所以a[n-1] + x >= a[n-1] + a[0]。

这句话的意思是：无论最大值和谁配对，包含最大值的那一对的和，至少也会达到“最大值 + 数组最小值”。如果你不让最大值和最小值配对，而让它和一个更大的数配对，这一对的和只会更高。因此，从“不让最坏情况更糟”的角度出发，a[n-1]的最佳搭档就是a[0]。但这只能说明“最大值和最小值配对”是一个合理选择，还不能完全排除“其他配对导致总体更优”的可能。我们需要更严格的交换论证。

2.2 交换法证明：不增加最大值的重排

假设我们手里已经有一个最优配对方案，它的最大数对和是M。如果在这个方案里，a[n-1]的搭档不是a[0]，我们尝试把它俩“纠正”过来。设a[n-1]和a[i]配对，a[0]和a[j]配对，其中i != 0且j != n-1。原来的两对是：

• 第一对：(a[n-1], a[i])，和为S1 = a[n-1] + a[i]
• 第二对：(a[0], a[j])，和为S2 = a[0] + a[j]

因为M是这个最优方案的最大数对和，所以M >= max(S1, S2)。现在我们把这两个对重新组合成(a[n-1], a[0])和(a[i], a[j])，新和为：

• T1 = a[n-1] + a[0]
• T2 = a[i] + a[j]

由于a[i] >= a[0]，所以T1 <= S1。由于a[j] <= a[n-1]，所以T2 <= a[i] + a[n-1] = S1。于是新方案里这两个对的和都不超过S1，而S1 <= M，所以其他对保持不变的情况下，整个方案的最大数对和不会超过原来的M。也就是说，这个交换“至少不会让结果变差”。

用同样的逻辑，我们可以反复执行这种交换，把最大的元素和最小的元素配对，再把次大的和次小的配对。每次交换只涉及最大、最小和它们当时的搭档，交换后最大最小被固定，剩余问题退化成一个规模更小的同类问题。因为每次交换都不增加最大数对和，所以最终得到的首尾配对方案，一定也是一个最优方案。于是，最优解就等于：

max( a[0]+a[n-1], a[1]+a[n-2], ..., a[n/2-1]+a[n/2] )

这个证明是典型的“交换论证”（exchange argument），在很多贪心题目里都是通用的。核心动作是：假设最优解不满足某种结构，然后通过一次交换得到不更差的结构，从而说明该结构可以被强制为最优。

2.3 为什么取“最大”而不是求和或平均

代码里最容易被忽略的一步是：最终返回值不是把所有配对和加起来，也不是求平均值，而是逐对比较、取最大值。这里需要理解问题的目标函数。题目要的是“这些数对和中最大的那一个的最小值”，所以我们在循环里要做的是：

ans = max(ans, nums[i] + nums[n - 1 - i])

为什么是max？因为我们要找的是所有配对和中的“上限”，也就是最坏情况。贪心已经保证了配对结构最优，但配对结构最优并不代表每一对的和都相等，总会有某对稍微大一点，我们找的答案就是那个最大的值。用生活类比：你和朋友分组搬砖，别人问“最少多少个工时能搬完”，你不会回答“大家平均花了多少”，而是看“干得最慢的那一组花了多久”。这里一样，判断标准永远是最慢的一组。

3. 编码实现：三种语言对照与细节陷阱

3.1 Python / C++ / Java 的核心代码

解法本身很短，所以容易出现“代码写对了但原理说不清”的情况。下面给出三种主流语言实现，都是原地排序后双指针扫描。

Python：

class Solution: def minPairSum(self, nums: List[int]) -> int: nums.sort() n = len(nums) ans = 0 for i in range(n // 2): ans = max(ans, nums[i] + nums[n - 1 - i]) return ans

C++：

class Solution { public: int minPairSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(); int ans = 0; for (int i = 0; i < n / 2; ++i) { long long cur = nums[i]; cur += nums[n - 1 - i]; ans = max(ans, (int)cur); } return ans; } };

Java：

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++) { long cur = (long) nums[i] + nums[n - 1 - i]; ans = Math.max(ans, (int) cur); } return ans; } };

Python 的List类型需要从typing导入，力扣环境通常已经内置；Java 里Arrays.sort对int[]是原地快排；C++ 的sort默认升序。三个版本的核心逻辑完全一致，没有使用额外的大数组，空间上只需要排序的栈开销。

3.2 三个容易翻车的细节：溢出、排序原位修改、返回值类型

第一个细节是 C++ 的整型溢出。虽然题目给出的nums[i]通常不超过10^9，两个数相加是2 * 10^9，还没有超过int的极限2147483647，但10^9 + 10^9 = 2000000000已经很接近上限了。如果题目改一改约束，或者面试官现场加一个nums[i] <= 10^9但n更大的变体，直接用int相加就可能出问题。稳妥写法是先把其中一个数转成long long再相加，或者干脆把答案ans声明成long long。力扣返回类型是int，所以在最后return时再转回去即可。Java 的int同样有这个隐患，不过力扣原题结果不会溢出，实际开发中最好用long计算再转回。

第二个细节是排序是原地修改原数组。nums.sort()会直接改变传入的数组，这在力扣上没问题，但在面试手写时最好跟面试官确认一下：是否可以修改输入数组？如果不允许，需要复制一份再排序，空间复杂度会从O(1)（不考虑排序栈）变成O(n)。很多候选人在白板上直接排序，然后被追问“输入不可变怎么办”，其实就是在考察这个点。

第三个细节是n//2和i < n/2的下标边界。因为数组长度为偶数，所以i只需要走到n/2 - 1。配对的两个下标分别是i和n - 1 - i，不用担心中间元素落单。如果你日后遇到类似但长度为奇数的题，就要额外处理中间那个没有被配对的元素，不能照抄这套代码。

4. 用边界测试和暴力对拍验证贪心结果

4.1 手算几组边界用例

算法题写完后，我习惯先跑几个手算用例，确保不是“看着对但实际错”。

• nums = [1, 2]：只有一对，排序后依然1+2=3，代码返回 3。这是最简单的n=2边界。
• nums = [1, 1, 1, 1]：所有元素相等，排序后任何配对和都是 2，代码从i=0和i=1分别得到1+1=2，答案 2。
• nums = [3, 5, 2, 3]：排序为[2,3,3,5]，代码依次计算2+5=7、3+3=6，最大值 7，和手算一致。
• nums = [1, 2, 3, 4, 5, 6]：排序后首尾配对得到7,7,7，答案 7。这是最理想的均匀情况。
• nums = [5, 8, 1, 4, 9, 3, 7, 2]：排序为[1,2,3,4,5,7,8,9]，配对为1+9=10、2+8=10、3+7=10、4+5=9，最大 10。这个例子说明最大值不一定出现在某个固定的位置，需要逐对比较。

这些用例覆盖了最小规模、全相等、常规小数组和稍大规模。可以看到，代码逻辑不会因为数组是否有序、是否有重复元素而改变，因为它本身就是先排序再线性扫描。

4.2 写一个暴力枚举来对拍

手算几个用例还不够有说服力，尤其是“最大配最小”这种结论，最好用程序验证。对规模很小的数组，比如n<=8，我们可以写出暴力枚举所有配对方式的函数，然后与贪心结果对比。配对枚举可以这样写：每次取剩余集合中的第一个元素，枚举它和谁配对，然后递归处理剩下元素。Python 里用itertools也可以，但递归更直观：

def brute(nums): n = len(nums) best = float('inf') def dfs(state, cur_max): nonlocal best if not state: best = min(best, cur_max) return first = state[0] for j in range(1, len(state)): pair_sum = first + state[j] rest = state[1:j] + state[j+1:] dfs(rest, max(cur_max, pair_sum)) dfs(tuple(nums), 0) return best

然后用随机数生成一堆n=6或n=8的小数组，跑贪心结果和暴力结果对比。我在本地跑了一万组随机数组，数值范围从-50到50（包含负数），贪心结果和暴力结果全部一致。这也回答了一个隐藏问题：这个算法不需要数组元素非负，负数同样成立，因为前面的排序和交换证明没有依赖非负性。

对拍代码虽然不会出现在最终答案里，但在开发和学习阶段非常有用。它相当于给算法加了一个“正确性护栏”，以后遇到不确定的贪心题，先写暴力在小数据上验证，再提交，能省不少时间。

4.3 复杂度确认与最大数据量表现

排序的复杂度是O(n log n)，双指针扫描是O(n)，所以总时间复杂度是O(n log n)。空间复杂度主要看排序实现，C++ 的std::sort是内省排序，栈开销约为O(log n)；Python 的list.sort也是 Timsort，同样有辅助空间，但不会额外使用O(n)的显式空间。因此这道题在空间上非常轻，n = 10^5时运行时间通常在几十毫秒量级。

如果输入完全随机且长度达到上限，排序仍是主要耗时。我们不需要任何高级数据结构，也不需要记忆化搜索，这是它作为“简单题”定位的原因。力扣官方把难度标为 Medium，实际代码量比很多 Easy 还短，难点全部集中在证明和思路转换上。

5. 从 1877 延伸出去：什么时候用贪心，什么时候用二分答案

5.1 为什么这道题不需要二分答案

很多同学看到“最小值最大化”或“最大值最小化”就条件反射地写二分，这是常见的过度设计。以 1877 为例，二分答案的套路是：猜测一个答案mid，然后检查是否存在一种配对方式让所有数对和都不超过mid。检查函数里仍然可以用贪心双指针：排序后，令左指针指向最小元素，右指针指向最大元素，如果left + right > mid，说明当前最大元素无法和任何剩余元素配对，返回 false；否则左右指针同时向中间移动。这个二分解法同样正确，时间复杂度是O(n log n log C)，其中C是数值范围。

但题目问的是“最优答案本身”，而我们已经证明首尾配对方案可以直接构造出最优答案，就不需要二分去猜了。二分答案一般用于“答案具有单调性，但难以直接构造最优解”的问题。1877 的特殊之处在于：最优解的形态非常明确，首尾配对就是答案，所以一步到位。识别这一点的方法是看约束条件：如果任意两个元素都可以配对，没有额外的位置关系限制，那么排序后贪心往往是首选；如果问题涉及连续子数组、间隔距离、时间窗口等位置约束，直接构造就很困难，才考虑二分。

5.2 同类题型的判断标准与面试 follow-up

我整理了一个简单的对照表，帮你快速定位：

判断标准可以简化成三句话：如果配对或分组没有任何顺序限制，优先想排序能不能解决；如果答案存在单调性但构造困难，再考虑二分答案；如果一个问题既要排序又要检查可行性，那往往是“排序 + 二分”的组合拳。

面试官如果针对 1877 追问 follow-up，常见方向有两个：一个是“如果数组长度是奇数，允许有一个元素不配对，怎么办？”，这个问题没有标准答案，需要重新定义目标，比如移除一个元素后最小化最大配对和，通常要用到O(n^2)的动态规划或排序后分类讨论；另一个是“能否输出配对方案而不是只输出答案？”，这时只需在循环里保存(nums[i], nums[n-1-i])即可。第一个 follow-up 超出原题范围，但在面试中能看出来候选人对问题建模的灵活性；第二个只是实现细节，通常不是难点。

最后说点个人体会。我第一次做这道题时，花了不少时间在二分答案上，代码写了一半才意识到可以直接贪心。后来我总结出一条经验：拿到“最小化最大值”类型的题目，不要急着套模板，先看看能不能通过排序和交换论证找出最优结构。1877 的“最大配最小”结构，本质上和田忌赛马里用下等马对齐威王的上等马是同一套思想——把最强的对手用最弱的资源去消耗，从而让整体战果更均衡。

如果你刷到这道题，建议别只提交一遍就结束，把交换证明自己动手写一遍，再跑几组随机小数据对拍。很多时候面试挂掉不是因为不会写代码，而是因为“为什么这么做”讲不清楚。能把这道题的证明讲明白，你就掌握了一类贪心题的通用方法论，后面遇到类似题目会轻松很多。