Medium

题目描述

给你一个整数数组 nums。

在一次移动中，你可以选择 nums 中的一个元素并将其更改为任何值。

返回在最多进行三次移动后，nums 中最大值和最小值之间的最小差值。

示例 1：

输入：nums = [5,3,2,4]
输出：0
解释：我们最多可以进行 3 次移动。
第一次移动，将 2 变为 3。nums 变为 [5,3,3,4]。
第二次移动，将 4 变为 3。nums 变为 [5,3,3,3]。
第三次移动，将 5 变为 3。nums 变为 [3,3,3,3]。
进行 3 次移动后，最小值和最大值之间的差值是 3 - 3 = 0。

示例 2：

输入：nums = [1,5,0,10,14]
输出：1
解释：我们最多可以进行 3 次移动。
第一次移动，将 5 变为 0。nums 变为 [1,0,0,10,14]。
第二次移动，将 10 变为 0。nums 变为 [1,0,0,0,14]。
第三次移动，将 14 变为 1。nums 变为 [1,0,0,0,1]。
进行 3 次移动后，最小值和最大值之间的差值是 1 - 0 = 1。
可以证明在 3 次移动中无法将差值变为 0。

示例 3：

输入：nums = [3,100,20]
输出：0
解释：我们最多可以进行 3 次移动。
第一次移动，将 100 变为 7。nums 变为 [3,7,20]。
第二次移动，将 20 变为 7。nums 变为 [3,7,7]。
第三次移动，将 3 变为 7。nums 变为 [7,7,7]。
进行 3 次移动后，最小值和最大值之间的差值是 7 - 7 = 0。

提示：

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

解题思路

这道题的核心思想是贪心策略。如果我们能进行最多3次移动来改变数组中的元素值，那么最优策略是改变那些对"最大值-最小值"差值影响最大的元素。

首先需要考虑特殊情况：如果数组长度小于等于4，那么我们可以通过3次移动将所有元素变为相同值，差值为0。

对于一般情况，排序后的数组中，最大值和最小值的差值主要由数组两端的元素决定。我们有四种策略：

  1. 移动3个最大值：结果差值为 nums[n-4] - nums[0]
  2. 移动2个最大值和1个最小值：结果差值为 nums[n-3] - nums[1]
  3. 移动1个最大值和2个最小值：结果差值为 nums[n-2] - nums[2]
  4. 移动3个最小值：结果差值为 nums[n-1] - nums[3]

我们需要尝试所有可能的组合，选择能产生最小差值的策略。这种方法的时间复杂度主要由排序决定，为O(n log n)。

代码实现

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        if (n <= 4) return 0;
        
        sort(nums.begin(), nums.end());
        
        int result = INT_MAX;
        // 移动3个最大值
        result = min(result, nums[n-4] - nums[0]);
        // 移动2个最大值，1个最小值
        result = min(result, nums[n-3] - nums[1]);
        // 移动1个最大值，2个最小值
        result = min(result, nums[n-2] - nums[2]);
        // 移动3个最小值
        result = min(result, nums[n-1] - nums[3]);
        
        return result;
    }
};

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 4:
            return 0
        
        nums.sort()
        
        # 四种策略：移动3个最大值，2大1小，1大2小，3个最小值
        return min(
            nums[n-4] - nums[0],   # 移动3个最大值
            nums[n-3] - nums[1],   # 移动2个最大值，1个最小值
            nums[n-2] - nums[2],   # 移动1个最大值，2个最小值
            nums[n-1] - nums[3]    # 移动3个最小值
        )

public class Solution {
    public int MinDifference(int[] nums) {
        int n = nums.Length;
        if (n <= 4) return 0;
        
        Array.Sort(nums);
        
        int result = int.MaxValue;
        // 移动3个最大值
        result = Math.Min(result, nums[n-4] - nums[0]);
        // 移动2个最大值，1个最小值
        result = Math.Min(result, nums[n-3] - nums[1]);
        // 移动1个最大值，2个最小值
        result = Math.Min(result, nums[n-2] - nums[2]);
        // 移动3个最小值
        result = Math.Min(result, nums[n-1] - nums[3]);
        
        return result;
    }
}

var minDifference = function(nums) {
    const n = nums.length;
    if (n <= 4) return 0;
    
    nums.sort((a, b) => a - b);
    
    // 四种策略：移动3个最大值，2大1小，1大2小，3个最小值
    return Math.min(
        nums[n-4] - nums[0],   // 移动3个最大值
        nums[n-3] - nums[1],   // 移动2个最大值，1个最小值
        nums[n-2] - nums[2],   // 移动1个最大值，2个最小值
        nums[n-1] - nums[3]    // 移动3个最小值
    );
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(1)

相关题目