908. 最小差值 I

Posted on | In
Words count in article: 301 | Reading time ≈ 1

题目

给你一个整数数组 A，对于每个整数 A[i]，我们可以选择处于区间 [-K, K] 中的任意数 x ，将 x 与 A[i] 相加，结果存入 A[i] 。

在此过程之后，我们得到一些数组 B。

返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

示例1：

1
2
3
输入：A = [1], K = 0
输出：0
解释：B = [1]

示例2：

1
2
3
输入：A = [0,10], K = 2
输出：6
解释：B = [2,8]

示例3：

1
2
3
输入：A = [1,3,6], K = 3
输出：0
解释：B = [3,3,3] 或 B = [4,4,4]

提示：

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

解法

解法一：

对数组排序，最大值和最小值的差值一定是A[A.length - 1] - K 和A[0] + K的差值。

如果这个差值小于0的话，那么最小差值就是0。因为A - B < 0 其实就是B - A > 0.那就还不是最小的。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
public int smallestRangeI(int[] A, int K) {
        if (0 == K) {
            if (1 == A.length) {
                return 0;
            } else {
                Arrays.sort(A);
                return A[A.length - 1] - A[0];
            }
        }
        Arrays.sort(A);
        int result = A[A.length - 1] - K - A[0] - K;
        return result < 0 ? 0 : result; 
    }
0%