解题报告-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:

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]

解题思路：

因为题目希望从所有数组B中，计算出所有最大值和最小值的差值，并从中取最小的差值

所以我们的目标是使数组B中的最大值尽可能小，最小值尽可能大

第一步确定最大值里，最小的，因为max元素最多只能减小到 max - K, 所以最大值不可能小于 max - K

第二步确定最小值里，最大的，因为min元素最多只能增加到 min + K, 所以最小值不可能大于 min + K

比较max - K 和 min + K

如果max - K <= min + K, 其他元素的取值范围正好可以覆盖[max - K, min + K]的区间, 因为每一个元素a[i], a[i] + K >= min + K, a[i] - K <= max - K

说明所有元素可以取到相同值，则最大值和最小值差距可以为0

如果max - K > min + K, 则由于最小的最大值为max - K, 最大的最小值为min + K,

则差距为 max - min - 2 * K

c++代码

class Solution {

public:

    //how to prove this process

    //min min + k

    //max max - k

    //如果min + k >= max - k 其它元素的取值范围一定是可以覆盖min + k, max - k

    //所以是最小值是0

    //如果min + k < max - k 则最大和最小的差值 = max - min - 2 * k

    int smallestRangeI(vector<int>& A, int K) {

        //edge case

        int minV = INT_MAX;

        int maxV = INT_MIN;

        for (int d : A) {

            minV = min(d, minV);

            maxV = max(d, maxV);

        }

        int ans = 0;

        if (maxV - K <= minV + K) return ans;

        return maxV - minV - 2 * K;

    }

};

java代码

class Solution {

    public int smallestRangeI(int[] A, int K) {

        int minV = Integer.MAX_VALUE;

        int maxV = Integer.MIN_VALUE;

        int ans = 0;

        for (int d : A) {

            minV = Math.min(minV, d);

            maxV = Math.max(maxV, d);

        }

        if (minV + K >= maxV - K) return ans;

        return maxV - minV - 2 * K;

    }

}

巴特西

解题报告-908. Smallest Range I

最新文章

热门文章