908. Smallest Range I

---

Description

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

---

Code

func smallestRangeI(nums []int, k int) int {
	min, max := nums[0], nums[0]
	
	for _, num := range nums {
		if num < min {
			min = num
		}
		if num > max {
			max = num
		}
	}

	if min+k >= max-k {
		return 0
	}

	return (max - k) - (min + k)
}

 

smallestRangeI 함수는 배열 nums의 모든 요소에 대해 최소한의 조정을 통해 배열의 최대값과 최소값의 차이를 k 이하로 만들 때, 조정해야 하는 최소값을 반환합니다.

주어진 코드는 먼저 배열 nums에서 최소값과 최대값을 찾습니다. 그런 다음, 최소값에 k를 더하고 최대값에 k를 뺀 값이 k보다 큰지 여부를 확인하여 조정이 필요한지를 결정합니다. 만약 최소값에 k를 더하고 최대값에 k를 뺀 값이 k 이상이면, 이미 최대값과 최소값의 차이가 k보다 작거나 같으므로 추가적인 조정이 필요하지 않습니다. 따라서 0을 반환합니다. 그렇지 않은 경우, 최대값에서 k를 뺀 값과 최소값에 k를 더한 값을 빼서 조정해야 하는 최소값을 계산하여 반환합니다.

주어진 코드의 시간 복잡도는 O(n)입니다. 배열 nums의 모든 요소를 한 번씩만 반복하므로 선형 시간이 소요됩니다.

만약 max - k가 min + k보다 작거나 같다면, 이미 최대값과 최소값의 차이가 k 이하이므로 조정이 필요하지 않습니다. 이 경우에는 0을 반환하고 있습니다. 그렇지 않은 경우에는 (max - k) - (min + k)를 반환하여 최대값과 최소값의 차이를 k 이하로 만들기 위해 조정해야 하는 최소값을 계산하고 있습니다.