LeetCode-Python-1509.三次操作后最大值与最小值的最小差（数组 + 数学）

给你一个数组 nums ，每次操作你可以选择 nums 中的任意一个数字并将它改成任意值。

请你返回三次操作后， nums 中最大值与最小值的差的最小值。

 

示例 1：

输入：nums = [5,3,2,4]
输出：0
解释：将数组 [5,3,2,4] 变成 [2,2,2,2].
最大值与最小值的差为 2-2 = 0 。
示例 2：

输入：nums = [1,5,0,10,14]
输出：1
解释：将数组 [1,5,0,10,14] 变成 [1,1,0,1,1] 。
最大值与最小值的差为 1-0 = 1 。
示例 3：

输入：nums = [6,6,0,1,1,4,6]
输出：2
示例 4：

输入：nums = [1,5,6,14,15]
输出：1
 

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

首先显然如果数组长度 <= 4，我们可以把所有数的值都变成一样，答案为0。

其次从数学的角度分析，给的三次处理机会应该用在最（较）大值或者最（较）小值上， 而且变化后的值应该最有利于结果。

而当数组长度 > 4 的时候，我们只会有四种处理的可能：

1. 变最小的三个数

2. 变最小的两个数和最大的数

3. 变最小数和两个最大数

4. 变三个最大数

遍历所有可能然后取答案里的最小值即可。

时间复杂度：O（NlogN）

空间复杂度：O（1）

class Solution(object):
    def minDifference(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 4:
            return 0
        nums.sort()
        # 1. 去前三个
        res = nums[-1] - nums[3]
        # 2. 去前两个和最后一个
        res = min(res, nums[-2] - nums[2])
        # 3. 去第一个和最后两个
        res = min(res, nums[-3] - nums[1])
        # 4. 去最后三个
        res = min(res, nums[-4] - nums[0])
        return res

推广到去除K个数：

class Solution(object):
    def minDifference(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 4:
            return 0
        nums.sort()
        res = float("inf")
        k = 3
        for i in range(k + 1):
            res = min(res, nums[-i - 1] - nums[k - i])
        return res