[LeetCode] 908. 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

最小差值 I。

给你一个整数数组 nums，和一个整数 k 。

在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。

nums 的 分数 是 nums 中最大和最小元素的差值。

在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。

思路

题意说你可以对 input 数组里任何一个数字修改一次，将 nums[i] 改为 nums[i] - x 和 nums[i] + x 范围中的任何一个数字，求 nums 中最大和最小元素的差值。

这道题有两种情况，一是 nums 中原先存在的 max 和 min 的差值就小于 2 * k，那么我们只需要把两者改为一样即可，返回 0。二是两者的差值大于 2 * k，那么结果就是 (max - k) - (min + k)。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        // corner case
        if (max == min) {
            return 0;
        }
        int diff = (max - k) - (min + k);
        return Math.max(0, diff);
    }
}