leetcode
leetcode 801 ~ 850
最小差值 I

最小差值 I

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 17.6 MB


/*
 * 题目思路:
 * 对于给定的数组 nums 和整数 k,可以对数组中的每个元素进行一次操作,
 * 该操作允许将元素增加或减少一个范围在 [-k, k] 内的整数。
 * 目标是使数组中的最大值和最小值的差值最小。
 * 实际上,可以将所有元素都加上 k 或减去 k,这样我们就只需要计算
 * max(nums) - k 和 min(nums) + k 之间的差值。
 */
import java.util.Arrays;
public int smallestRangeI(int[] nums, int k) {
    int min = Arrays.stream(nums).min().orElse(Integer.MAX_VALUE);
    int max = Arrays.stream(nums).max().orElse(Integer.MIN_VALUE);
    return Math.max(0, max - min - 2 * k);
}

解释

方法:

题解的核心思路是通过调整数组中元素的值来最小化数组中最大值和最小值的差值。首先通过计算数组中的最大值和最小值,然后考虑将最小值增加最多k,将最大值减少最多k,从而尝试减少这两者之间的差。计算调整后的差值为 (max(nums) - k) - (min(nums) + k) = max(nums) - min(nums) - 2*k。然后,取上述差值与0的最大值,以确保不返回负数,因为分数不能是负的。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到的操作是`将最小值增加最多k,将最大值减少最多k`,这是否确保了在所有情况下都能达到最小的分数差?
是的,这样的操作在大多数情况下确实能达到最小的分数差。这种方法的目的是尽可能缩小最大值和最小值之间的距离。通过将最小值增加至多k,以及将最大值减少至多k,我们实质上是在尽量使数组的范围靠拢。然而,如果两者之间的差距小于或等于2k,那么最大值和最小值可以完全重合或非常接近,从而使差值变为0或非常小。
🦆
题解假设了`max(nums) - min(nums) - 2 * k`可以直接应用,但如果`k`的值非常大,超过了`max(nums) - min(nums)`的一半,这种情况下该公式是否还适用?
如果`k`的值非常大,超过了`max(nums) - min(nums)`的一半,那么公式`max(nums) - min(nums) - 2 * k`会得到一个负数。这是因为减少的总量(2 * k)会超出最大值和最小值之间的原始差值。在这种情况下,按照题解中的公式,最终的差值会通过`max(0, max_val - min_val - 2 * k)`计算,确保不会返回负数,而是返回0。这意味着,即使k值非常大,公式仍然适用,因为我们通过取最大值来处理负数情况,确保最小差值不会小于0。
🦆
题解中计算最终分数时使用了`max(0, max_val - min_val - 2 * k)`,为什么要与0取最大值,结果会出现负数的情况吗?
是的,结果可能出现负数。这种情况发生在当k的值非常大时,特别是当k大到可以使得调整后的最小值大于或等于调整后的最大值时。此时`max(nums) - min(nums) - 2 * k`的计算结果会是负数。为了确保算法返回一个合理的、非负的分数差,我们使用`max(0, ...)`来确保任何负数结果都会被修正为0。
🦆
题解中没有使用额外的数组或数据结构,但是是否可以考虑使用其他数据结构来优化算法的性能或是使代码更加简洁?
在这个特定的问题中,使用额外的数据结构可能不会带来明显的性能提升或代码简洁性,因为本质上我们只需要计算数组中的最大值和最小值,这可以通过简单的一次遍历实现。加入额外的数据结构如堆(用于动态获取最大值和最小值)或排序数组可能会增加实现的复杂度,而不一定带来效率上的提升。当前算法的时间复杂度已经是O(n),这是因为计算最大值和最小值各需要一次遍历,而空间复杂度是O(1),这已经是最优解了。

相关问题