大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

经常看我题解的同学都知道，我每次都上来先分析题目意思，这是做对题的第一步。

本题是说对于数组中的每个元素，都可以对其值进行修改：加上 [-k, k] 内的任意整数。问如何对整个数组修改后，数组的最大值减去最小值的差，是最小的。

举个例子，假如输入数组是 [3, 6]，k = 2。

那么对于 3 来说，可以变成 [1, 2 ,3, 4, 5] 中的一个：

那么对于 6 来说，可以变成 [4, 5 ,6, 7, 8] 中的一个：

因此，可以把数组 [3, 6]变成 [4, 4] 或者 [5, 5]，此时的最大值和最小值相等，即差值为 0。

解题方法

对于本题，我的第一想法是把最小值 + k，最大值 - k，修改后的数组最大值与最小值的差“应该是”最小的。

转念一想，不对啊！假如 最小值 + k > 最大值 - k，经过上面的转化，矮的变成高的了、高的变成矮的了。其实本来差值可以变成 0 的，但是却导致「矫枉过正」了。

因此，思路就有了：

  • 当原数组的最大值 - 最小值 > 2 * k，那么把最小值 + k，最大值 - k，得到的新数组的最大值和最小值的差最小。
  • 否则，得到的新数组的最大值和最小值的差就是 0。（不要「矫枉过正」）
  1. class Solution(object):
  2.     def smallestRangeI(self, nums, k):
  3.         """
  4.         :type nums: List[int]
  5.         :type k: int
  6.         :rtype: int
  7.         """
  8.         diff = max(nums) - min(nums)
  9.         if diff > 2 * k:
  10.             return diff - 2 * k
  11.         return 0

复杂度

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

    总结

  1. 对于这种题目，并不需要真正的把“新数组”的每个值都计算出来，只需要求出一个值来，那么一般就是靠思路和规律取胜，不要暴力求“新数组”哦~

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。