1.题目描述
给你一个数组
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。
2.解题思路
通过题意可以发现，我们只能操作数组中的三个数字，如果这个数组中元素的个数<=4，那么我们任意将三个数修改为相同的值都能保证最大值和最小值为同一个数，即最小差为0
对于数组中元素个数>4的情况，我们可以先把数组按照递增排序，可以发现我们所有可能的操作情况是有限的，例如我们可以把前三小的元素都改成第四小的元素，那么此时的最小差就是nums[n-1]-nums[3]；又或者我们可以将前三大的元素修改成第四大的元素，那么数组的最小差就是nums[n-4]-nums[0]；这些情况可以用nums[n-4+i]-nums[i]概括，其中i的范围为[0,3]
3.代码实现
class Solution {public int minDifference(int[] nums) {int n = nums.length;if (n <= 4) return 0;Arrays.sort(nums);int res = Integer.MAX_VALUE;for (int i = 0 ; i <= 3; i++) {res = Math.min(res,nums[n-4+i] - nums[i]);}return res;}
}
