LeetCode 1877.数组中最大数对和的最小值｜贪心算法详解（多解法+代码全覆盖）

LeetCode 1877.数组中最大数对和的最小值｜贪心算法详解（多解法+代码全覆盖）

一、题目详细描述

1.1 题目题意

给定一个长度为偶数 n的整数数组nums，需要将数组中所有元素两两配对，最终得到n/2个数对。

定义：

• 数对和：数对\(a,b\)的和为a \+ b

• 最大数对和：所有数对和中的最大值

要求：找到最优的配对方案，使得最大数对和尽可能小，最终返回该最小的最大数对和。

1.2 样例解析

示例 1：

输入：nums = \[3,5,2,3\]

输出：7

最优配对：\(3,3\)、\(5,2\)，数对和分别为6、7，最大值为7。

任何其他配对方式的最大数对和都会大于等于7。

示例 2：

输入：nums = \[3,5,4,2,4,6\]

输出：8

最优配对：\(3,5\)、\(4,4\)、\(6,2\)，所有数对和均为8，最大数对和为8。

1.3 题目约束

• n == nums\.length，且n为偶数

• 2 \<= n \<= 10^5

• 1 \<= nums\[i\] \<= 10^5

关键点：数据量最大为10510^5105，暴力枚举绝对超时，必须使用线性/线性对数级别的算法。

二、解题核心思想（贪心原理证明）

2.1 核心贪心策略

本题是经典的最小化最大值贪心问题，最优策略为：

数组排序后：最小值 + 最大值、次小值 + 次大值，两两配对

所有配对和中的最大值，即为答案。

2.2 贪心正确性证明

假设数组升序排序后为：a0 ≤ a1 ≤ a2 ≤ \.\.\. ≤ an\-1

反证法：如果不采用「最小配最大」的方式，一定会出现更大的数对和。

• 若将大数与大数配对：会直接产生极大的数对和，最大值飙升；

• 若将小数与小数配对：剩余的大数只能互相配对，依然会产生更大的和；

• 唯一能均衡所有数对和的方式：大小互补配对，抹平极值差距，让所有数对和尽可能接近，最终最大值最小。

结论：排序后首尾两两配对是唯一最优解。

三、解法一：暴力回溯枚举（入门理解｜超时）

3.1 思路讲解

遍历数组所有可能的两两配对组合，枚举全部配对方案，计算每种方案的最大数对和，最终记录最小值。

适合新手理解题意，但时间复杂度极高，仅用于学习，无法通过大数据用例。

3.2 完整代码

fromtypingimportListclassSolution:defminPairSum(self,nums:List[int])->int:n=len(nums)used=[False]*n min_max_sum=float('inf')defbacktrack(count,current_max):nonlocalmin_max_sum# 所有数对配对完成，更新答案ifcount==n//2:min_max_sum=min(min_max_sum,current_max)return# 找到第一个未使用的元素i=0whilei<nandused[i]:i+=1used[i]=True# 遍历后续所有未使用的元素配对forjinrange(i+1,n):ifnotused[j]:used[j]=Truenew_max=max(current_max,nums[i]+nums[j])backtrack(count+1,new_max)used[j]=Falseused[i]=Falsebacktrack(0,0)returnmin_max_sum

3.3 复杂度分析

• 时间复杂度：O((n−1)!!)O((n-1)!!)O((n−1)!!)，双重阶乘，数据量n=20时就会超时

• 空间复杂度：O(n)O(n)O(n)，递归栈+标记数组

适用场景：仅用于理解题目配对逻辑，刷题禁用。

四、解法二：排序+遍历枚举（基础贪心｜可AC）

4.1 思路讲解

基于贪心结论：数组排序后，首尾两两配对最优。

实现步骤：

1. 对数组进行升序排序；

2. 左指针从0开始，右指针从数组末尾开始；

3. 依次计算nums\[left\] \+ nums\[right\]，记录所有和的最大值；

4. 最终最大值即为最小的最大数对和。

4.2 完整AC代码（标准版）

fromtypingimportListclassSolution:defminPairSum(self,nums:List[int])->int:# 数组升序排序nums.sort()n=len(nums)max_sum=0# 首尾配对遍历foriinrange(n//2):current_sum=nums[i]+nums[n-1-i]ifcurrent_sum>max_sum:max_sum=current_sumreturnmax_sum

4.3 极简一行优化版

fromtypingimportListclassSolution:defminPairSum(self,nums:List[int])->int:nums.sort()returnmax(nums[i]+nums[~i]foriinrange(len(nums)//2))

小技巧：nums\[\~i\]等价于nums\[\-i\-1\]，快速取倒数第i个元素，代码更简洁。

五、解法三：排序+双指针（进阶优化｜最优可读性）

5.1 思路讲解

在贪心基础上，使用左右双指针遍历，逻辑更清晰、适配拓展场景，是工程中最常用的写法。

• 左指针left：指向当前未配对的最小值

• 右指针right：指向当前未配对的最大值

• 每次配对后，左指针右移、右指针左移，直到配对完成

5.2 完整AC代码（双指针版）

fromtypingimportListclassSolution:defminPairSum(self,nums:List[int])->int:nums.sort()left=0right=len(nums)-1res=0# 双指针首尾配对whileleft<right:current=nums[left]+nums[right]res=max(res,current)left+=1right-=1returnres

5.3 复杂度分析（最优解法）

• 时间复杂度：O(nlogn)O(nlogn)O(nlogn)，瓶颈为数组排序，遍历仅需O(n)O(n)O(n)

• 空间复杂度：O(logn)O(logn)O(logn)，排序递归栈空间（原地排序）

该解法可完全通过10510^5105数据量测试，时间效率最优。

六、三种解法全方位对比

七、高频易错点总结

• 误区1：认为随便配对可以得到最优解。
  纠正：只有大小互补配对才能最小化最大值，同类数字配对一定会结果更差。

• 误区2：想通过暴力枚举解题。
  纠正：数据量最大10510^5105，暴力法完全无法通过，必须贪心。

• 误区3：排序后顺序两两配对（相邻配对）。
  纠正：相邻配对会导致大数相加，最大数对和变大，属于错误解法。

• 边界易错：数组长度为2时，直接两数相加即为答案，算法可天然兼容无需特判。

八、算法思想延伸（面试拓展）

本题属于经典的最小化最大值贪心模型，同类高频面试题：

1. 分割数组的最大值

2. 装载问题最小载重

3. 二分答案+最大化最小值/最小化最大值系列问题

核心解题思维：想要让极值最优，必须均衡分配资源/数值，避免极端值叠加。

九、全文总结

1. 本题核心考点：贪心算法，核心策略为排序后首尾大小互补配对；

2. 摒弃暴力解法，掌握排序+遍历、排序+双指针两种最优AC解法；

3. 解题模板通用：所有「最小化最大和/最大化最小值」问题均可参考均衡贪心思路；

4. 时间复杂度瓶颈为排序O(nlogn)O(nlogn)O(nlogn)，是本题最优时间复杂度。