Question

910. Smallest Range II

中文文档

Description

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

For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k.

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

Return _the minimum score of _nums_ after changing the values at each index_.

 

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: 3
Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.

 

Constraints:

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

Solutions

Solution 1: Greedy + Enumeration

According to the problem requirements, we need to find the minimum difference between the maximum and minimum values in the array. Each element can be increased or decreased by $k$, so we can divide the elements in the array into two parts, one part increased by $k$ and the other part decreased by $k$. Therefore, we should decrease the larger values in the array by $k$ and increase the smaller values by $k$ to ensure the minimum difference between the maximum and minimum values.

Therefore, we can first sort the array, then enumerate each element in the array, divide it into two parts, one part increased by $k$ and the other part decreased by $k$, and calculate the difference between the maximum and minimum values. Finally, take the minimum value among all differences.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$, where $n$ is the length of the array.

class Solution:
  def smallestRangeII(self, nums: List[int], k: int) -> int:
    nums.sort()
    ans = nums[-1] - nums[0]
    for i in range(1, len(nums)):
      mi = min(nums[0] + k, nums[i] - k)
      mx = max(nums[i - 1] + k, nums[-1] - k)
      ans = min(ans, mx - mi)
    return ans

class Solution {
  public int smallestRangeII(int[] nums, int k) {
    Arrays.sort(nums);
    int n = nums.length;
    int ans = nums[n - 1] - nums[0];
    for (int i = 1; i < n; ++i) {
      int mi = Math.min(nums[0] + k, nums[i] - k);
      int mx = Math.max(nums[i - 1] + k, nums[n - 1] - k);
      ans = Math.min(ans, mx - mi);
    }
    return ans;
  }
}

class Solution {
public:
  int smallestRangeII(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int ans = nums[n - 1] - nums[0];
    for (int i = 1; i < n; ++i) {
      int mi = min(nums[0] + k, nums[i] - k);
      int mx = max(nums[i - 1] + k, nums[n - 1] - k);
      ans = min(ans, mx - mi);
    }
    return ans;
  }
};

func smallestRangeII(nums []int, k int) int {
  sort.Ints(nums)
  n := len(nums)
  ans := nums[n-1] - nums[0]
  for i := 1; i < n; i++ {
    mi := min(nums[0]+k, nums[i]-k)
    mx := max(nums[i-1]+k, nums[n-1]-k)
    ans = min(ans, mx-mi)
  }
  return ans
}