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

给你一个下标从 0 开始的整数数组 nums 。

• nums 的 最小 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
• nums的 最大 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
• nums 的分数是 最大 得分与 最小 得分的和。

我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。

请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。

|x| 表示 x 的绝对值。

示例 1：

**输入：** nums = [1,4,3]
**输出：** 0
**解释：** 将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。

示例 2：

**输入：** nums = [1,4,7,8,5]
**输出：** 3
**解释：** 将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 109

下午两点【biIibiIi@灵茶山艾府】直播讲题，记得关注哦~

---

根据题意，修改成 nums 中的数字，可以让最小得分为 0。那么分数就等于最大得分。

那么从小到大排序后，我们可以：

• 修改最大的两个数为 nums}[n-3]，最大得分为 nums}[n-3]-\textit{nums}[0]；
• 修改最小的为 nums}[1]，最大的为 nums}[n-2]，最大得分为 nums}[n-2]-\textit{nums}[1]；
• 修改最小的两个数为 nums}[2]，最大得分为 nums}[n-1]-\textit{nums}[2]。

这样修改的理由是，修改成再更大/更小的数，不会影响最大得分了。

[sol1-Python3]

class Solution:
    def minimizeSum(self, a: List[int]) -> int:
        a.sort()
        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])

[sol1-Go]

func minimizeSum(a []int) int {
	sort.Ints(a)
	n := len(a)
	return min(min(a[n-3]-a[0], a[n-2]-a[1]), a[n-1]-a[2])
}

func min(a, b int) int { if a > b { return b }; return a }

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。手动维护或者用快速选择可以做到 O(n)。
• 空间复杂度：O(1)。忽略排序时栈的开销，仅用到若干额外变量。