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

发表于： 分类于：
字数： 682 阅读：≈ 2分钟

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

给你一个数组 nums 。

每次操作你可以选择 nums 中的任意一个元素并将它改成 任意值 。

在 执行最多三次移动后 ，返回 nums 中最大值与最小值的最小差值。

思路

基本思想

只能修改三个，必须找到一个目标值修改，修改之后要求最值之间的差最小，第一想法就是排序，然后要么将最大值改小，要么把最小值改大，这样可以使得最值之间的差变小

修改时，需要注意要把尽可能小和尽可能大的数进行修改，所以有以下四种情况：

  1. 修改3小0大
  2. 修改2小1大
  3. 修改1小2大
  4. 修改0小3大

修改之后分别对应的最值为：

1
2
3
4
5

//nums已经拍过序
int res1=nums[nums.length-1]-nums[3];
int res2=nums[nums.length-2]-nums[2];
int res3=nums[nums.length-3]-nums[1];
int res4=nums[nums.length-4]-nums[0];

如果看不明白，可以把修改看成删除，因为修改之后的元素变成某一个目标元素，此时最值变到了新的位置，例如删除1小2大之后，最小值变到了nums[1]的位置，最大值变到了nums[nums.length-3]的位置，此时直接计算二者的差即可，最后返回四种情况的最小值

执行流程

  1. 将数组排序
  2. 计算四种情况的结果
  3. 返回四种结果中的最小值

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    //要么大变小，要么小变大（考虑的不全面）
    //变化其实可以理解为删除，所以：
    //要么删除3小0大
    //要么删除2小1大
    //要么删除1小2大
    //要么删除0小3大
    public int minDifference(int[] nums) {
        //少于5个数时，三步之内一定可以变成全相同的数
        if(nums.length<5)
            return 0;

        //要么大变小，要么小变大，这种思路很暴力
        Arrays.sort(nums);
        int res1=nums[nums.length-1]-nums[3];
        int res2=nums[nums.length-2]-nums[2];
        int res3=nums[nums.length-3]-nums[1];
        int res4=nums[nums.length-4]-nums[0];

        //返回四种情况的最小值
        int res=Integer.MAX_VALUE;
        res=res>res1?res1:res;
        res=res>res2?res2:res;
        res=res>res3?res3:res;
        res=res>res4?res4:res;

        return res;
    }
}

总结

主要是要有贪心的思想，修改的只能是最值，不然差距不可能变小，因为最终的结果是由当前的最值计算得到的