友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

给你一个数组 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 <= 105

  • -109 <= nums[i] <= 109

思路分析

先对数组进行排序,要求最大值与最小值的最小差值,那么就是把减少最大值和最小值直接的差值,要么把最大值变小,要么把最小值变大,或者两者都要。所以,就要看那种方式能对差值改变最大。

看官方题解,可以直接求 \(a(n - 4 + i) - a(i)\) 的最小值。

  • 一刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-05-21 22:54:47
 */
public int minDifference(int[] nums) {
  int length = nums.length;
  if (length <= 4) {
    return 0;
  }
  Arrays.sort(nums);
  int diff = nums[length - 1] - nums[0];
  int max = 0;
  // max = Math.max(max, (nums[3] - nums[0]) + (nums[length - 1] - nums[length - 1]));
  // max = Math.max(max, (nums[2] - nums[0]) + (nums[length - 1] - nums[length - 2]));
  // max = Math.max(max, (nums[1] - nums[0]) + (nums[length - 1] - nums[length - 3]));
  // max = Math.max(max, (nums[0] - nums[0]) + (nums[length - 1] - nums[length - 4]));
  for (int i = 3; i >= 0; i--) {
    max = Math.max(max, (nums[i] - nums[0]) + (nums[length - 1] - nums[length - (4 - i)]));
  }
  return diff - max;
}