leetcode：908. 最小差值 I

港控/mmm° 2023-03-13 06:18 119阅读 0赞

# 题目来源 #

[leetcode][]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

> 分析：

*  本题目目的是找到最小差值，先注意一点，题目要求A里的**每个树都要被进行某种运算后加入到B中**，然后返回**B中的最大值和B的最小值的差值**，如果不加最大最小的限定，这道题目就没有意义了，因为不这样的话，任何有数的数组的**最小**差值都是0（自己减自己，其他的数值直接忽略）

在要操作**每个数**的前提下，为了找到最小差值，我们需要找到数组的两个极端值，忽略掉其他的值，因为题目要求我们这样做（**先别考虑±K**）。我们首先需要找到**最大最小值**，标在数轴上，如果忽略掉题目给的条件K，此时求最小差值(或者说唯一差值)就是max-min，也就是**也就是图中min点到max点距离**，但是题目给了一个数域\[-k，k\]，要求我们返回在max和min在±k域中的数后，返回形成组合中差值中**最小**的，这里我们把min±k后形成的范围，叫做min域，max叫做max域，注意，这两已经不是点了。此时所谓的最小差值，就是**min域的右边界到max域的左边界的距离**，翻译成数学式子就是：(max - K) - (min + K)，化简后就是max - min - 2 \* k。这里需要注意的一点就是，结果为负数的情况，负数的情况体现在图上就是左右边界相交的情况，此时 **最小值应返回0，而非负数**。

> 分析

*  把A中的数字放置在数轴上，B中的数字由A中数字加x组成，-K <= X <= K。
 *  为了使得B的最大值和最小值之间差值最小，即B区间长度最小。
 *  可以将给A的最小值加K，给A的最大值减K，B区间的长度最小为0或者A区间长度减2K。
 *  minmax\_element 可以在线性时间内得到 A 最小值和最大值的迭代器。

class Solution {
        
    public:
        int smallestRangeI(const vector<int>& A, const int K) {
        
            if (A.empty()) return 0;
            const auto [low, high] = minmax_element(A.begin(), A.end());
            return max(0, *high - *low - 2 * K);
        }
    };

> (max - k) - (min - k) = max - min - 2k

public static int smallestRangeI(int[] A, int K) {
        
            Arrays.sort(A);
            return Math.max(0, A[A.length - 1] - A[0] - 2 * K);
        }

![在这里插入图片描述][20200512135959357.png]

public static int smallestRangeI(int[] A, int K) {
        
            int max = A[0];
            int min = A[0];
            for (int i = 1; i < A.length; i++){
        
                if (A[i] > max){
        
                    max = A[i];
                }
    
                if (A[i] < min){
        
                    min = A[i];
                }
            }
            return Math.max(0, max - min - 2 * K);
        }

![在这里插入图片描述][20200512140205497.png]

[leetcode]: https://leetcode-cn.com/problems/smallest-range-i/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230312/0b5f31b93b154103b270e3d6958ec51d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20230312/7307b1de5dc14092ac61b4180ae2b815.png
[20200512135959357.png]: /images/20230312/a92bbdde3e6a450fb1d8b7c3bc3dd739.png
[20200512140205497.png]: /images/20230312/e4dbc71e886b48fab8a47a11de5a0cf5.png