欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-01 14:58:44
...

链接

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

思路

参考谭光志

由于是求最大值与最小值的最小差值,所以要尽量让最大值和最小值接近,首先需要对数组进行排序。

1 2 3 4 5 6 7 8 9 10

用上面的例子来做参考:

  1. 如果不能修改值,直接用最大值减去最小值就是结果 10 - 1
  2. 如果能修改一个值,就有两种可能:10 - 2(修改N[0])    9 - 1(修改N[n-1])
  3. 如果能修改两个值,就有三种可能:10 - 3(修改N[0]和N[1])    9 - 2(修改N[0]和N[N-1])   8 - 1(修改N[n-1]和N[n-2])
  4. 如果能修改三个值,就有四种可能:10 - 4(修改N[0]、N[1]、N[2])    9 - 3(N[0]、N[1]、N[n-1])    8 - 2(N[0]、N[n-1]、N[n-2])    7 - 1(N[n-1]、N[n-2]、N[n-3])

比较所有的可能值,取其中最小的值就是结果。

C++ Code

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        if (n <= 4) return 0;
        return min({nums[n-1] - nums[3], nums[n-2] - nums[2], nums[n-3] - nums[1], nums[n-4] - nums[0]});
        }
};