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

标签: 贪心 数组 排序

难度: 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 <= 105
  • -109 <= nums[i] <= 109

Submission

运行时间: 55 ms

内存: 26.8 MB

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if (n := len(nums)) <= 4:
            return 0
        
        if n > 32:
            mx = nlargest (4, nums)
            mn = nsmallest(4, nums)
        else:
            nums.sort()
            mx = nums[-4:][::-1]
            mn = nums[:4]
        
        return min(mx[i] - mn[3-i] for i in range(4))

Explain

题解的核心思路是最小化数组中的最大值和最小值之间的差，通过至多改变三个元素的值。考虑到只需要关注数组中的四个最大值和四个最小值，因为数组中任何大于四个元素的改变都可以被这四个最大或最小值所覆盖。如果数组长度小于或等于4，直接返回0，因为可以将所有元素改为相同的值。如果数组很大，为了效率直接使用堆（或其他方法）来找到这四个最大和四个最小的值。然后考虑所有可能的场景：改变0个，1个，2个或3个元组中最大或最小的元素，并计算可能的最小差值。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if (n := len(nums)) <= 4:
            return 0  # 如果长度小于等于4，可以直接将所有元素变为相同的值
        
        if n > 32:
            mx = nlargest(4, nums)  # 获取最大的4个值
            mn = nsmallest(4, nums)  # 获取最小的4个值
        else:
            nums.sort()
            mx = nums[-4:][::-1]  # 排序后取最后四个数，即最大的四个数
            mn = nums[:4]  # 同理取前四个数，即最小的四个数
        
        return min(mx[i] - mn[3-i] for i in range(4))  # 计算可以通过改变0到3个元素达到的最小差值

Explore

在这个问题中，目标是最小化数组中的最大值和最小值之间的差。考虑到最多只能改变三个元素，因此关注数组中的最大四个值和最小四个值是因为这些值定义了最大和最小的边界。如果改变数组中任何不在这八个值中的其他元素，不会直接影响到最大值和最小值的边界，因此不会对最终的最大值与最小值的差产生影响。换句话说，只有通过改变这些边界值，才能有效地减小最大值和最小值之间的差距。

在处理大于32个元素的数组时，使用堆来找到最大和最小的四个值是出于效率考虑。堆操作允许以对数时间复杂度插入和删除元素，特别是使用最小堆和最大堆可以直接访问最小值和最大值。这种方法比完整排序数组更高效，因为完整排序的时间复杂度为O(n log n)，而使用堆找到几个最大或最小的元素只需要O(n log k)，其中k是堆的大小。在本题中，k为4，所以使用堆是一个更快的解决方案。

这种计算方式是尝试所有可能的改变最大值和最小值的组合。具体来说，`mx[i]`表示在保留最大的第i个元素的情况下，`mn[3-i]`表示在保留最小的第(4-i)个元素的情况下。这样的组合考虑了从全部保留最大值（即i=3时，保留最大的4个元素中的最大元素，同时改变最小的一个元素）到全部保留最小值（即i=0时，改变最大的3个元素，保留最小的4个元素中的最小元素）的所有场景。通过这种方式，我们可以计算出通过改变0到3个元素所能达到的最小的最大值与最小值的差，从而找到最小差值。

在数组长度小于或等于4的情况下，直接返回0是正确的。因为题目允许我们改变至多三个元素的值，如果数组长度为4或更少，我们可以选择将所有元素改变为数组中任一元素的值，从而使最大值和最小值相等，差为0。不存在使这一假设不成立的特殊情况，因为无论初始数组的元素如何，我们总是有足够的操作次数来使所有元素相等。