Formatted question description: https://leetcode.ca/all/910.html
910. Smallest Range II
Level
Medium
Description
Given an array A
of integers, for each integer A[i]
we need to choose either x = -K
**or x = K
, and add x
to A[i]
(only once).
After this process, we have some array B
.
Return the smallest possible difference between the maximum value of B
and the minimum value of B
.
Example 1:
Input: A = [1], K = 0
Output: 0
Explanation: B = [1]
Example 2:
Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]
Example 3:
Input: A = [1,3,6], K = 3
Output: 3
Explanation: B = [4,6,3]
Note:
1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000
Solution
First sort the array A
, find the maximum element and the minimum element and calculate the difference.
Next consider whether each number should be added K
or -K
. For any two numbers num1
and num2
, if num1 < num2
, then adding K
to num1
and adding -K
to num2
is always optimal.
After A
is sorted, find the maximum index i
such that A[i]
should be added K
, and the minimum difference can be obtained.
-
class Solution { public int smallestRangeII(int[] A, int K) { Arrays.sort(A); int length = A.length; int min = A[0], max = A[length - 1]; int difference = max - min; for (int i = 1; i < length; i++) { int num1 = A[i - 1], num2 = A[i]; int high = Math.max(A[length - 1] - K, num1 + K); int low = Math.min(A[0] + K, num2 - K); difference = Math.min(difference, high - low); } return difference; } }
-
Todo
-
class Solution(object): def smallestRangeII(self, A, K): """ :type A: List[int] :type K: int :rtype: int """ A.sort() N = len(A) mn, mx = A[0], A[-1] res = mx - mn for i in range(N - 1): mx = max(A[i] + 2 * K, mx) mn = min(A[i + 1], A[0] + 2 * K) res = min(mx - mn, res) return res