跳转至

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

解题思路#

将数组排序后，一共有四种情况：

  • nums[-1] - nums[3] \(\Leftarrow\) nums[0]、nums[1]、nums[2] 变为 nums[3]
  • nums[-2] - nums[2] \(\Leftarrow\) nums[0]、nums[1] 变为 nums[2]，nums[-1] 变为 nums[-2]
  • nums[-3] - nums[1] \(\Leftarrow\) nums[0] 变为 nums[1]，nums[-1]、nums[-2] 变为 nums[-3]
  • nums[-4] - nums[0] \(\Leftarrow\) nums[-1]、nums[-2]、nums[-3] 变为 nums[-4]

答案即为上面 4 中情况中的最小值。

先排序，后枚举。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0

        nums.sort()

        ans = -2 * 10 ** 9
        for i in range(4):
            ans = min(ans, nums[i - 4] - nums[i])

        return ans

使用优先队列维护最小的 4 个数和最大的 4 个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import heapq


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0

        max_four = heapq.nlargest(4, nums)
        min_four = heapq.nsmallest(4, nums)

        ans = 2 * 10 ** 9
        for i in range(4):
            ans = min(ans, max_four[i] - min_four[3 - i])

        return ans
测试数据
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
solution = Solution()

nums = [5, 3, 2, 4]
assert solution.minDifference(nums) == 0

nums = [1, 5, 0, 10, 14]
assert solution.minDifference(nums) == 1

nums = [6, 6, 0, 1, 1, 4, 6]
assert solution.minDifference(nums) == 2

nums = [1, 5, 6, 14, 15]
assert solution.minDifference(nums) == 1

print("PASS!")
返回顶部

在手机上阅读