Medium

题目描述

对 (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 中每个元素 恰好在一个 对中，并且
  • 最大 对和的值最小。

请你在完成优化配对后，返回最小化的 最大对和。

示例 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 。

提示：

  • n == nums.length
  • 2 <= n <= 10^5
  • n 是偶数
  • 1 <= nums[i] <= 10^5

解题思路

解题思路

这是一个经典的贪心算法问题。要让最大对和尽可能小，我们需要找到最优的配对策略。

核心观察：

  • 为了最小化最大对和，我们应该避免将两个很大的数配对在一起
  • 最优策略是让最大的数和最小的数配对，次大的数和次小的数配对，以此类推

算法步骤：

  1. 首先将数组排序
  2. 使用双指针技术：左指针指向最小值，右指针指向最大值
  3. 每次将最小值和最大值配对，计算它们的和
  4. 记录所有配对中的最大值，这就是答案

为什么这样是最优的？ 设排序后的数组为 [a1, a2, ..., an]，其中 a1 ≤ a2 ≤ ... ≤ an。

  • 最大值 an 必须与某个数配对，为了让包含 an 的对和尽可能小，应该让它与最小值 a1 配对
  • 同理，次大值 an-1 应该与次小值 a2 配对
  • 这样的配对方式能够最大程度地"中和"大小值的差异，从而最小化最大对和

时间复杂度主要来自排序，双指针遍历是线性的。

代码实现

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        int maxSum = 0;
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            maxSum = max(maxSum, nums[left] + nums[right]);
            left++;
            right--;
        }
        
        return maxSum;
    }
};

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        
        max_sum = 0
        left, right = 0, len(nums) - 1
        
        while left < right:
            max_sum = max(max_sum, nums[left] + nums[right])
            left += 1
            right -= 1
        
        return max_sum

public class Solution {
    public int MinPairSum(int[] nums) {
        Array.Sort(nums);
        
        int maxSum = 0;
        int left = 0, right = nums.Length - 1;
        
        while (left < right) {
            maxSum = Math.Max(maxSum, nums[left] + nums[right]);
            left++;
            right--;
        }
        
        return maxSum;
    }
}

var minPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    
    let maxSum = 0;
    let left = 0, right = nums.length - 1;
    
    while (left < right) {
        maxSum = Math.max(maxSum, nums[left] + nums[right]);
        left++;
        right--;
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：主要消耗在排序上，为 O(n log n)；双指针遍历为 O(n)
  • 空间复杂度：只使用了常数额外空间，排序可能需要 O(log n) 的栈空间，但通常认为是 O(1)