What is the optimal way to minimize the difference in this problem?

The optimal way is to perform three moves on the extreme values (either the three smallest or three largest) to reduce the difference between the maximum and minimum values.

How do I handle edge cases in this problem?

For arrays with fewer than four elements, no move is needed, and the answer is simply the difference between the maximum and minimum values.

Why is sorting necessary for solving this problem?

Sorting allows easy access to the smallest and largest values in the array, making it simple to apply the greedy approach for minimizing the difference.

What happens if I allow more than three moves?

Allowing more than three moves would change the problem significantly, as it would require handling more than just the extreme elements, potentially leading to a higher time complexity.

How does the greedy strategy work in this problem?

The greedy strategy works by minimizing the maximum difference by removing the most extreme values in the array. By choosing the largest and smallest elements to adjust, you achieve the minimum difference with the least number of moves.

#1509

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个数组 nums 。每次操作你可以选择 nums 中的任意一个元素并将它改成任意值。在执行最多三次移动后，返回 nums 中最大值与最小值的最小差值。示例 1：输入： nums = [5,3,2,4] 输出： 0 解释：我们最多可以走 3 步。第一步，将 2 变为 3 。 …

数组贪心排序

题目描述

给你一个数组 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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 贪心

我们可以先判断数组长度是否小于 $5$ ，如果小于 $5$ ，那么直接返回 $0$ 。

否则，我们将数组排序，然后贪心地选择数组左边最小的 $l=[0,..3]$ 个数和右边最小的 $r = 3 - l$ 个数，取其中最小的差值 $nums[n - 1 - r] - nums[l]$ 即可。

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

相似题目：

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

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 5:
            return 0
        nums.sort()
        ans = inf
        for l in range(4):
            r = 3 - l
            ans = min(ans, nums[n - 1 - r] - nums[l])
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for a candidate who can efficiently implement the greedy approach.
question_mark
The candidate should demonstrate an understanding of the impact of sorting on time complexity.
question_mark
A good candidate will consider edge cases where fewer than four elements are present in the array.

warning

常见陷阱

外企场景

error
Failing to recognize that only three moves are allowed, and thus choosing more elements than necessary.
error
Not considering edge cases where the array is too small to perform any moves.
error
Overlooking the importance of sorting the array for efficient calculation of possible differences.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than three moves and testing the impact on time complexity.
arrow_right_alt
Implementing the solution without sorting, using a more efficient selection method.
arrow_right_alt
Using a dynamic programming approach to test all combinations of three changes.

help

常见问题

外企场景

继续练习

#1481 不同整数的最少数目 #1465 切割后面积最大的蛋糕 #1561 你可以获得的最大硬币数目