LeetCode 题解工作台
最小差值 I
给你一个整数数组 nums ，和一个整数 k 。 在一个操作中，您可以选择 0 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。 nums 的 分数 是 nums 中最大和最…
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·数学
答案摘要
根据题目描述，我们可以将数组中的最大值减去 ，最小值加上 ，这样可以使得数组中的最大值和最小值之差变小。 因此，最终的答案就是 $\max(\textit{nums}) - \min(\textit{nums}) - 2 \times k$ 和 之间的较大值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数数组 nums，和一个整数 k 。
在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。
nums 的 分数 是 nums 中最大和最小元素的差值。
在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。
示例 1：
输入：nums = [1], k = 0 输出：0 解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。
示例 2：
输入：nums = [0,10], k = 2 输出：6 解释：将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。
示例 3：
输入：nums = [1,3,6], k = 3 输出：0 解释：将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 1040 <= k <= 104
解题思路
方法一：数学
根据题目描述，我们可以将数组中的最大值减去 ，最小值加上 ，这样可以使得数组中的最大值和最小值之差变小。
因此，最终的答案就是 和 之间的较大值。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def smallestRangeI(self, nums: List[int], k: int) -> int:
mx, mi = max(nums), min(nums)
return max(0, mx - mi - k * 2)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests how well the candidate can leverage mathematical operations and array manipulation to minimize a range.
- question_mark
Checks if the candidate can quickly identify the importance of adjusting boundary elements for optimal results.
- question_mark
Evaluates the candidate's ability to handle edge cases like single-element arrays or when k is zero.
常见陷阱
外企场景- error
Overcomplicating the solution by trying to adjust every element, when only the largest and smallest need to be changed.
- error
Failing to handle edge cases, such as arrays with only one element or k being zero.
- error
Misunderstanding the problem and adjusting elements outside the required range [-k, k].
进阶变体
外企场景- arrow_right_alt
Modifying the problem to allow multiple operations per element.
- arrow_right_alt
Adding constraints where k can change dynamically throughout the process.
- arrow_right_alt
Introducing additional conditions, like maintaining a specific average of the elements.