---

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

• 标签：贪心、数组、排序
• 难度：中等

题目链接

• 1509. 三次操作后最大值与最小值的最小差 - 力扣

题目大意

描述：给定一个数组 $nums$。最多可以进行 $3$ 次操作，每次操作可以将任意一个元素改成任意值。

要求：返回经过最多 $3$ 次操作后，数组最大值与最小值之间可能的最小差值。

说明：

• $1 \le nums.length \le 10^5$。
• $-10^9 \le nums[i] \le 10^9$。

示例：

• 示例 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。

解题思路

思路 1：排序 + 枚举

1. 核心思想

改变一个元素可以消除它成为最大值或最小值的可能性。目标是使最大值和最小值的差尽可能小。

最多改 $3$ 个元素，相当于我们可以从两侧移除最多 $3$ 个极值（要么去掉最小的几个，要么去掉最大的几个）。

排序后，枚举所有可能的移除方案：

• 移除最小的 $0$ 个和最大的 $3$ 个：跨度 $nums[n-4] - nums[0]$。
• 移除最小的 $1$ 个和最大的 $2$ 个：跨度 $nums[n-3] - nums[1]$。
• 移除最小的 $2$ 个和最大的 $1$ 个：跨度 $nums[n-2] - nums[2]$。
• 移除最小的 $3$ 个和最大的 $0$ 个：跨度 $nums[n-1] - nums[3]$。

取最小值即可。

2. 具体步骤

第 1 步：排序 $nums$。如果 $n \le 4$，可以全改成同一个值，差为 $0$。

第 2 步：枚举 $i = 0 \to 3$：

• $ans = min(ans, nums[n - 4 + i] - nums[i])$。

第 3 步：返回 $ans$。

3. 举例说明

以 $nums = [5,3,2,4,6,1,7]$ 为例：

排序后 $[1,2,3,4,5,6,7]$，$n=7$。

• 去 $3$ 大：$[1,2,3,4]$，差 $4-1=3$。
• 去 $1$ 小 $2$ 大：$[2,3,4,5]$，差 $5-2=3$。
• 去 $2$ 小 $1$ 大：$[3,4,5,6]$，差 $6-3=3$。
• 去 $3$ 小：$[4,5,6,7]$，差 $7-4=3$。

最小差 $3$。

以 $nums = [1,5,0,10,14]$ 为例：

排序后 $[0,1,5,10,14]$，$n=5$。

• 去 $3$ 大：$[0,1,5]$，差 $5-0=5$。
• 去 $1$ 小 $2$ 大：$[1,5,10]$，差 $10-1=9$。
• 去 $2$ 小 $1$ 大：$[5,10,14]$，差 $14-5=9$。
• 去 $3$ 小：$[10,14]$，差 $14-10=4$。

最小差 $4$。

思路 1：代码

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        nums.sort()
        n = len(nums)
        ans = float('inf')
        for i in range(4):
            ans = min(ans, nums[n - 4 + i] - nums[i])
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，排序。
• 空间复杂度：$O(1)$。