1877. 数组中最大数对和的最小值

• 标签：贪心、数组、双指针、排序
• 难度：中等

题目链接

• 1877. 数组中最大数对和的最小值 - 力扣

题目大意

描述：一个数对 $(a, b)$ 的数对和等于 $a + b$。最大数对和是一个数对数组中最大的数对和。

• 比如，如果我们有数对 $(1, 5)$，$(2, 3)$ 和 $(4, 4)$，最大数对和为 $max(1 + 5, 2 + 3, 4 + 4) = max(6, 5, 8) = 8$。

给定一个长度为偶数 $n$ 的数组 $nums$，现在将 $nums$ 中的元素分为 $n / 2$ 个数对，使得：

• $nums$ 中每个元素恰好在一个数对中。
• 最大数对和的值最小。

要求：在最优数对划分的方案下，返回最小的最大数对和。

说明：

• $n == nums.length$。
• $2 \le n \le 10^5$。
• $n$ 是偶数。
• $1 \le nums[i] \le 10^5$。

示例：

• 示例 1：

输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2)。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7。

• 示例 2：

输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2)。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8。

解题思路

思路 1：排序 + 贪心

为了使最大数对和的值尽可能的小，我们应该尽可能的让数组中最大值与最小值组成一对，次大值与次小值组成一对。而其他任何方案都会使得最大数对和的值更大。

那么，我们可以先将数组进行排序，然后首尾依次进行组对，并计算这种方案下的最大数对和即为答案。

思路 1：代码

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

思路 1：复杂度分析

• 时间复杂度：$O(n \times \log n)$。
• 空间复杂度：$O(\log n)$。