原文链接: https://leetcode-cn.com/problems/smallest-range-i

英文原文

You are given an integer array nums and an integer k.

In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after applying the mentioned operation at most once for each index in it.

 

Example 1:

Input: nums = [1], k = 0
Output: 0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2:

Input: nums = [0,10], k = 2
Output: 6
Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.

Example 3:

Input: nums = [1,3,6], k = 3
Output: 0
Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 104
• 0 <= k <= 104

中文题目

给你一个整数数组 nums，请你给数组中的每个元素 nums[i] 都加上一个任意数字 x （-k <= x <= k），从而得到一个新数组 result 。

返回数组 result 的最大值和最小值之间可能存在的最小差值。

 

示例 1：

输入：nums = [1], k = 0
输出：0
解释：result = [1]

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：result = [2,8]

示例 3：

输入：nums = [1,3,6], k = 3
输出：0
解释：result = [3,3,3] or result = [4,4,4]

 

提示：

• 1 <= nums.length <= 10000
• 0 <= nums[i] <= 10000
• 0 <= k <= 10000

通过代码

官方题解

方法 1：数学

想法和算法

假设 A 是原始数组，B 是修改后的数组，我们需要最小化 max(B) - min(B)，也就是分别最小化 max(B) 和最大化 min(B)。

max(B) 最小可能为 max(A) - K，因为 max(A) 不可能再变得更小。同样，min(B) 最大可能为 min(A) + K。所以结果 max(B) - min(B) 至少为 ans = (max(A) - K) - (min(A) + K)。

我们可以用一下修改方式获得结果（如果 ans >= 0）：

• 如果 $A[i] \leq \min(A) + K$，那么 $B[i] = \min(A) + K$
• 如果 $A[i] \geq \max(A) - K$，那么 $B[i] = \max(A) - K$
• 否则 $B[i] = A[i]$。

如果 ans < 0，最终结果会有 ans = 0，同样利用上面的修改方式。

[]
class Solution {
    public int smallestRangeI(int[] A, int K) {
        int min = A[0], max = A[0];
        for (int x: A) {
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
        return Math.max(0, max - min - 2*K);
    }
}

[]
class Solution(object):
    def smallestRangeI(self, A, K):
        return max(0, max(A) - min(A) - 2*K)

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是 A 的长度。
• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
21744	31131	69.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言