Question

1509. 三次操作后最大值与最小值的最小差

English Version

题目描述

给你一个数组 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 <= 105
• -109 <= nums[i] <= 109

解法

方法一：排序 + 贪心

我们可以先判断数组长度是否小于 $5$，如果小于 $5$，那么直接返回 $0$。

否则，我们将数组排序，然后贪心地选择数组左边最小的 $l=[0,..3]$ 个数和右边最小的 $r = 3 - l$ 个数，取其中最小的差值 $nums[n - 1 - r] - nums[l]$ 即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 nums 的长度。

相似题目：

• 2567. 修改两个元素的最小分数

class Solution:
  def minDifference(self, nums: List[int]) -> int:
    n = len(nums)
    if n < 5:
      return 0
    nums.sort()
    ans = inf
    for l in range(4):
      r = 3 - l
      ans = min(ans, nums[n - 1 - r] - nums[l])
    return ans

class Solution {
  public int minDifference(int[] nums) {
    int n = nums.length;
    if (n < 5) {
      return 0;
    }
    Arrays.sort(nums);
    long ans = 1L << 60;
    for (int l = 0; l <= 3; ++l) {
      int r = 3 - l;
      ans = Math.min(ans, (long) nums[n - 1 - r] - nums[l]);
    }
    return (int) ans;
  }
}

class Solution {
public:
  int minDifference(vector<int>& nums) {
    int n = nums.size();
    if (n < 5) {
      return 0;
    }
    sort(nums.begin(), nums.end());
    long long ans = 1L << 60;
    for (int l = 0; l <= 3; ++l) {
      int r = 3 - l;
      ans = min(ans, 1LL * nums[n - 1 - r] - nums[l]);
    }
    return ans;
  }
};

func minDifference(nums []int) int {
  n := len(nums)
  if n < 5 {
    return 0
  }
  sort.Ints(nums)
  ans := 1 << 60
  for l := 0; l <= 3; l++ {
    r := 3 - l
    ans = min(ans, nums[n-1-r]-nums[l])
  }
  return ans
}