Medium

题目描述

给你一个整数数组 nums。

  • nums 的低分是任意两个整数之间的最小绝对差值。
  • nums 的高分是任意两个整数之间的最大绝对差值。
  • nums 的分数是高分和低分的总和。

返回改变 nums 中两个元素后的最小分数。

示例 1：

输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 改为 6，使 nums 变为 [6,6,7,8,5]。
低分是最小绝对差值：|6 - 6| = 0。
高分是最大绝对差值：|8 - 5| = 3。
高分和低分的总和是 3。

示例 2：

输入：nums = [1,4,3]
输出：0
解释：
将 nums[1] 和 nums[2] 改为 1，使 nums 变为 [1,1,1]。
最大绝对差值和最小绝对差值的总和是 0。

约束条件：

  • 3 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这是一道贪心算法题目。我们需要理解两个关键点：

  1. 最小绝对差值（低分）：要让最小绝对差值尽可能小，最好的策略是让两个相邻元素变得相等，这样最小差值就是0。

  2. 最大绝对差值（高分）：要让最大绝对差值尽可能小，需要缩小整个数组的范围，即减少最大值和最小值之间的差距。

核心思路：

  • 对数组进行排序，这样最大值和最小值分别在两端
  • 我们可以改变两个元素，最优策略是改变数组的极值（最大或最小的几个元素）
  • 有三种主要策略：
    1. 改变两个最小值：让它们等于第三小的值
    2. 改变两个最大值：让它们等于第三大的值
    3. 改变一个最小值和一个最大值：分别等于第二小和第二大的值

分析三种情况： 排序后，设数组为 [a, b, c, ..., x, y, z]

  1. 情况1：改变 a, b 为 c，新的高分是 z - c，低分是 0
  2. 情况2：改变 y, z 为 x，新的高分是 x - a，低分是 0
  3. 情况3：改变 a 为 b，改变 z 为 y，新的高分是 y - b，低分是 0

取三种情况的最小值即可。

代码实现

class Solution {
public:
    int minimizeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        // 三种策略的结果
        int option1 = nums[n-1] - nums[2];  // 改变两个最小值
        int option2 = nums[n-3] - nums[0];  // 改变两个最大值
        int option3 = nums[n-2] - nums[1];  // 改变一个最小值和一个最大值
        
        return min({option1, option2, option3});
    }
};

class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        
        # 三种策略的结果
        option1 = nums[n-1] - nums[2]  # 改变两个最小值
        option2 = nums[n-3] - nums[0]  # 改变两个最大值
        option3 = nums[n-2] - nums[1]  # 改变一个最小值和一个最大值
        
        return min(option1, option2, option3)

public class Solution {
    public int MinimizeSum(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        
        // 三种策略的结果
        int option1 = nums[n-1] - nums[2];  // 改变两个最小值
        int option2 = nums[n-3] - nums[0];  // 改变两个最大值
        int option3 = nums[n-2] - nums[1];  // 改变一个最小值和一个最大值
        
        return Math.Min(Math.Min(option1, option2), option3);
    }
}

var minimizeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    
    // 三种策略的结果
    const option1 = nums[n-1] - nums[2];  // 改变两个最小值
    const option2 = nums[n-3] - nums[0];  // 改变两个最大值
    const option3 = nums[n-2] - nums[1];  // 改变一个最小值和一个最大值
    
    return Math.min(option1, option2, option3);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(1)只使用常数额外空间（排序为原地排序）