What is the key to solving the Minimum Score by Changing Two Elements problem?

The key is to minimize the difference between the maximum and minimum values by changing the largest and smallest elements, which can be efficiently done with a greedy approach.

How does sorting help in the Minimum Score by Changing Two Elements problem?

Sorting allows you to quickly identify the largest and smallest elements in the array, making it easy to apply the greedy strategy and minimize the score.

What are some edge cases to consider in this problem?

Edge cases include very small arrays, arrays with identical values, and arrays where one change results in the minimal score.

Can this problem be solved without sorting the array?

While sorting simplifies the process, you can also solve the problem by manually identifying the maximum and minimum values, though this may increase complexity.

What is the time complexity of the optimal solution for this problem?

The optimal solution has a time complexity of O(n log n) due to the sorting step, followed by constant time operations for validation.

#2567

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

修改两个元素的最小分数

给你一个下标从 0 开始的整数数组 nums 。 nums 的最小得分是满足 0 的 |nums[i] - nums[j]| 的最小值。 nums 的最大得分是满足 0 的 |nums[i] - nums[j]| 的最大值。 nums 的分数是最大得分与最小得分的和。我们的目标是最…

数组贪心排序

题目描述

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 贪心

根据题意我们知道，最小得分实际上是排序数组相邻两个元素的最小差值，最大得分是排序数组首尾元素的差值。数组 $nums$ 的分数是最小得分与最大得分的和。

因此，我们可以先对数组进行排序。由于题目允许我们修改数组中最多两个元素的值，我们可以通过修改一个数，让其跟数组中的另一个数相同，使得最小得分为 $0$ ，那么数组 $nums$ 的分数实际上就是最大得分。我们可以选择进行如下修改之一：

修改最小的两个数为 $nums[2]$ ，那么最大得分为 $nums[n - 1] - nums[2]$ ；
修改最小的一个数为 $nums[1]$ ，最大的一个数为 $nums[n - 2]$ ，那么最大得分为 $nums[n - 2] - nums[1]$ ；
修改最大的两个数为 $nums[n - 3]$ ，那么最大得分为 $nums[n - 3] - nums[0]$ 。

最后，我们返回上述三种修改的得分的最小值即可。

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

相似题目：

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

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	complexity is dependent on the sorting step, which is O(n log n), and space complexity is O(n) for the array processing. The greedy approach and invariant validation add minimal overhead.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate focuses on adjusting the extremes of the array for minimization.
question_mark
The candidate can correctly explain the impact of sorting and greedy choices.
question_mark
The candidate handles edge cases effectively and ensures correctness through validation.

warning

常见陷阱

外企场景

error
Ignoring the importance of modifying the extremes (max and min) first.
error
Not validating the final array after changes, potentially leading to incorrect results.
error
Failing to account for edge cases such as very small arrays or large values.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing more than two elements and observing the impact on score.
arrow_right_alt
Handling arrays with only one possible change, where the result is trivial.
arrow_right_alt
Optimizing for specific constraints such as arrays with repeated elements.

help

常见问题

外企场景

继续练习

#2576 求出最多标记下标 #2554 从一个范围内选择最多整数 I #2551 将珠子放入背包中