LeetCode偶尔一题 —— 908. 最小差值 I

原题地址:https://leetcode-cn.com/problems/smallest-range-i/

题目描述

题目分析

原题描述稍微有点绕,用更加通俗易懂的语言描述就是:

给出一个整数 k,找到一个整数 x 且整数 x 满足 -k <= x <= k,与 A[i] 相加之后得到数组 B。我们得到的就是数组 B 中最大值与最小值的最小差值

要得到最大值与最小值的最小差值,那么就应该让最大值尽可能小,最小值尽可能大。

a最大值b最小值,那么应该满足:
a - k 尽可能小,b + k 尽可能大
所以:最小差值 s = (a - k) - (b + k) = a - b - 2k >= 0

示例代码

1
2
3
4
5
6
7
8
9
10
/**
* @param {number[]} A
* @param {number} K
* @return {number}
*/
var smallestRangeI = function(A, K) {
const min = Math.min(...A)
const max = Math.max(...A)
return Math.max(0, max - min - 2 * K)
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)