Question

Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add xto A[i].

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: 0 Explanation: B = [3,3,3] or B = [4,4,4]

Note:

1. 1 <= A.length <= 10000
2. 0 <= A[i] <= 10000
3. 0 <= K <= 10000

Difficulty:Easy

Category:Math

Analyze

这道题目的输入是一个整数的集合以及一个目标数值k,要求对于A[i]的任何一个元素，我们都可以选择一个-K <= x <= K的整数，并將藏歌整数加入到这个集合里面去，找到每一项中加入的数值的最大值和最小值的最小差。(其实就是向中间值靠拢)

Solution

// Solution:
// Runtime: 20ms
class Solution {
 public:
  int smallestRangeI(vector<int>& A, int K) {
    int ma = *std::max_element(A.begin(), A.end());
    int mi = *std::min_element(A.begin(), A.end());

    return max(0, ma - mi - 2 * K);
  }
};

稍微修改一下：

// Solution:
// Runtime: 20ms
class Solution {
 public:
  int smallestRangeI(vector<int>& A, int K) {
    int ma = 0, mi = INT_MAX;
    for (int& i : A) {
      ma = max(ma, i);
      mi = min(mi, i);
    }
    return max(0, ma - mi - 2 * K);
  }
};