leetcode-908-Smallest-Range-I

发表于   |  

描述

Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add x to 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:

1
2
3
Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

1
2
3
Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]

Example 3:

1
2
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

分析

题目大意是 A 数组里的每个值可以加上一个 x，(-K <= x <= K)，对 A 数组所有数字进行这样的操作之后得到新数组 B，求可能得到的最小的 B 最大值和最小值之差。

要想要这个差最小，那么最大值和最小值应该尽可能靠拢，最好的情况可能是最大值减 K，最小值加 K，如果最大值减 K 减去最小值加 K 的结果大于零，那么结果为最大值减 K 减去最小值加 K 的结果，否则这个结果就是零。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int smallestRangeI(int[] A, int K) {
        int min = A[0], max = A[0];
        for (int i: A) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        return Math.max(max-min-2*K, 0);
    }
}

题目来源