力扣908题最小差值I：数学思维与极值调整的Python高效解法

在算法刷题的过程中我们常常会遇到一类看似简单实则暗藏数学巧思的题目。力扣LeetCode第908题「最小差值 I」就是其中的典型代表。很多同学初次看到题目描述时可能会觉得一头雾水或者尝试用复杂的排序、遍历去解决结果要么超时要么代码冗长。本文将为你彻底拆解这道题揭示其背后的数学本质并提供清晰、高效的Python解决方案。无论你是正在准备面试的求职者还是希望提升算法思维的学生掌握这道题的解法都能让你对“极值”和“范围”类问题有更深的理解。1. 问题背景与核心概念1.1 问题描述与官方链接力扣第908题「最小差值 I」的官方描述如下 给你一个整数数组nums和一个整数k。 对于数组中的每个下标i0 i nums.length我们可以将nums[i]的值修改为范围在[nums[i] - k, nums[i] k]内的任意整数。该操作最多只能进行一次。 我们的目标是通过修改或不修改数组中的每个元素使得修改后数组的“最大值”与“最小值”之间的差值最小化。 请你返回在执行上述操作后数组可能的最小差值。示例 1输入nums [1], k 0 输出0 解释数组只有一个元素最大值和最小值都是1差值为0。示例 2输入nums [0, 10], k 2 输出6 解释可以将数组修改为 [2, 8]。最大值8与最小值2的差值为6。示例 3输入nums [1, 3, 6], k 3 输出0 解释可以将数组修改为 [3, 3, 3]。最大值和最小值相等差值为0。1.2 核心概念什么是“最小差值”这道题的核心在于理解“操作”的实质。题目允许我们对数组中的每一个元素独立地进行一次调整调整的范围是以该元素原始值为中心上下浮动k个单位。这意味着对于任意一个元素nums[i]其最终可能的值是一个区间[nums[i] - k, nums[i] k]。我们的目标是通过为每个元素在这个区间内选择一个最终值使得整个数组的最大值与最小值的差尽可能小。这听起来像是一个复杂的组合优化问题但如果我们深入思考其数学本质会发现一个非常简洁的规律。1.3 为什么这道题值得学习思维转换它训练你将一个看似需要遍历所有可能性的问题转化为一个基于极值的数学计算问题。理解极值深刻理解数组的“最大值”和“最小值”在允许波动下的行为。面试高频这类考察数学思维和问题简化能力的题目在笔试和面试中非常常见。代码简洁最优解法通常只需要几行代码是体现算法功力的好题目。2. 解题思路分析与数学推导直接对每个元素进行枚举修改显然是不现实的。我们需要找到问题的关键。2.1 思路启发考虑两个极端情况让我们先考虑数组中的两个特殊元素原始数组的最大值max_num和最小值min_num。对于最小值min_num我们最多能将它增加k变为min_num k。对于最大值max_num我们最多能将它减少k变为max_num - k。我们的核心目标是缩小max_num和min_num之间的距离。2.2 数学推导与核心公式设原始数组的最大值为max_val最小值为min_val。在允许修改的情况下可能的最小值是多少最小值min_val最多只能增加到min_val k。因此整个数组修改后可能的最小值new_min至少是min_val但我们可以尝试让它变大最大不会超过min_val k。实际上new_min可以是min_val到min_val k之间的任意值但为了缩小与最大值的差距我们通常希望new_min尽可能大。同理可能的最大值是多少最大值max_val最多只能减少到max_val - k。因此整个数组修改后可能的最大值new_max至多是max_val但我们可以尝试让它变小最小不会低于max_val - k。为了缩小差距我们通常希望new_max尽可能小。那么最优策略是什么我们努力让最小值变大让最大值变小。如果它们调整后的范围有重叠我们甚至可以让它们相等调整后的最小值范围[min_val, min_val k]调整后的最大值范围[max_val - k, max_val]如果(min_val k) (max_val - k)说明这两个区间有重叠。我们完全可以选择一个值让它同时落在两个区间内从而使new_min等于new_max。此时最小差值就是0。如果(min_val k) (max_val - k)说明无论我们怎么调整最小值能到达的最高点仍然低于最大值能到达的最低点。它们之间始终存在一个“无法跨越的鸿沟”。此时我们最优的做法是将最小值提升到最高 (min_val k)将最大值降低到最低 (max_val - k)。此时的最小差值就是(max_val - k) - (min_val k) max_val - min_val - 2 * k。综上所述最小差值的计算公式为max(0, (max_val - min_val) - 2 * k)这个max(0, ...)确保了当差值可能为负数时即区间重叠时我们取0。2.3 思路验证用之前的例子验证示例1:nums[1], k0。max_val1, min_val1。差值 max(0, (1-1) - 2*0) max(0, 0) 0。正确。示例2:nums[0,10], k2。max_val10, min_val0。差值 max(0, (10-0) - 2*2) max(0, 10-4) max(0, 6) 6。正确。示例3:nums[1,3,6], k3。max_val6, min_val1。差值 max(0, (6-1) - 2*3) max(0, 5-6) max(0, -1) 0。正确。3. 环境准备与代码实现3.1 环境说明编程语言Python 3.x。本题解不依赖任何第三方库使用Python内置函数即可。代码编辑器/IDE任意你熟悉的工具即可如 VS Code, PyCharm, Jupyter Notebook。力扣刷题环境你可以在力扣官网直接使用其在线编辑器。3.2 核心函数实现根据上述推导代码实现极其简洁。我们只需要找到数组的最大值和最小值然后套用公式即可。class Solution: def smallestRangeI(self, nums: List[int], k: int) - int: 计算执行操作后数组可能的最小差值。 参数: nums (List[int]): 输入的整数数组。 k (int): 允许每个元素调整的最大幅度。 返回: int: 可能的最小差值。 # 步骤1: 找到数组中的最大值和最小值 max_val max(nums) min_val min(nums) # 步骤2: 应用核心公式计算最小差值 # max(0, (原始极差) - 2*k) result max(0, (max_val - min_val) - 2 * k) return result3.3 代码逐行解析def smallestRangeI(self, nums: List[int], k: int) - int:这是力扣题目要求的函数签名包含类型注解清晰明了。max_val max(nums)和min_val min(nums)使用Python内置的max()和min()函数以O(n)的时间复杂度遍历数组一次实际上max()和min()各遍历一次总体仍是 O(n)找到极值。这是效率最高的方法。result max(0, (max_val - min_val) - 2 * k)这是算法的核心。max_val - min_val计算原始数组的极差。减去2 * k表示我们试图通过调整将极差缩小2k最小值加k最大值减k。max(0, ...)确保结果非负。如果计算出的差值为负说明极差可以完全消除最小差值就是0。return result返回计算结果。3.4 复杂度分析时间复杂度O(n)。其中 n 是数组nums的长度。我们只需要遍历数组两次分别求最大值和最小值或者一些优化实现可以一次遍历同时找到最大最小值但复杂度仍是 O(n)。空间复杂度O(1)。我们只使用了常数级别的额外空间几个变量与输入数组的大小无关。4. 测试用例与运行验证为了确保代码的正确性我们需要设计多种边界情况和典型场景进行测试。# 测试代码 def test_smallestRangeI(): solution Solution() # 测试用例1: 单元素数组k0 assert solution.smallestRangeI([1], 0) 0, 测试用例1失败 print(测试用例1通过: nums[1], k0 - 0) # 测试用例2: 示例2 assert solution.smallestRangeI([0, 10], 2) 6, 测试用例2失败 print(测试用例2通过: nums[0,10], k2 - 6) # 测试用例3: 示例3差值可降为0 assert solution.smallestRangeI([1, 3, 6], 3) 0, 测试用例3失败 print(测试用例3通过: nums[1,3,6], k3 - 0) # 测试用例4: 所有元素相同k任意 assert solution.smallestRangeI([5, 5, 5, 5], 10) 0, 测试用例4失败 print(测试用例4通过: nums[5,5,5,5], k10 - 0) # 测试用例5: k非常大足以让任何元素变成任何值相对而言 # 原始极差为 100-199 2*k 200 99-200 -101 max(0, -101)0 assert solution.smallestRangeI([1, 50, 100], 100) 0, 测试用例5失败 print(测试用例5通过: nums[1,50,100], k100 - 0) # 测试用例6: k0即不允许修改 assert solution.smallestRangeI([4, 7, 2, 9], 0) 7, 测试用例6失败 # 9-27 print(测试用例6通过: nums[4,7,2,9], k0 - 7) # 测试用例7: 普通情况差值不能降为0 # 极差90-1080, 2*k30, 80-3050 assert solution.smallestRangeI([10, 30, 60, 90], 15) 50, 测试用例7失败 print(测试用例7通过: nums[10,30,60,90], k15 - 50) print(\n所有测试用例通过) # 运行测试 if __name__ __main__: # 注意需要将上面的Solution类定义包含进来 test_smallestRangeI()将上述测试代码与Solution类放在同一个文件中运行你会看到所有测试通过的输出。这验证了我们算法逻辑的正确性。5. 常见错误与思维误区在解决这道题时初学者容易陷入以下几个误区5.1 误区一尝试修改所有元素的值错误想法“我需要为每个nums[i]决定一个具体的修改值然后计算新数组的极差再找最小值。”分析这种思路会导致组合爆炸。数组有n个元素每个元素有(2k1)种可能如果k小搜索空间巨大。题目并没有要求输出具体的修改方案只要求最小差值因此这是一个典型的优化问题往往存在数学规律无需枚举。5.2 误区二只关注最大值和最小值但策略错误错误想法“我把最大值减小k最小值增加k然后计算新差值(max-k) - (mink)就行了。”分析这个想法接近了但忽略了关键情况——当(max - k)可能小于(min k)时计算出的差值会是负数这在实际的差值中是没有意义的。差值最小就是0。因此必须用max(0, ...)来保证结果的正确性。这是本题最易错的点。5.3 误区三使用排序错误代码示例def smallestRangeI_wrong(nums, k): nums.sort() # 不必要的排序O(n log n) 复杂度 return max(0, (nums[-1] - nums[0]) - 2*k)分析虽然这段代码能得到正确结果但其时间复杂度是O(n log n)因为排序操作。而通过max()和min()函数只需要O(n)的时间。在算法题中应选择最优解法。排序在这里是多余且低效的。5.4 误区四误解“最多进行一次操作”错误理解认为整个数组只能修改一次或者每个元素只能被修改一次但必须选择同一个k值。正确理解题目意思是对于每个下标 i你可以选择对 nums[i] 进行一次修改操作修改到其允许的范围内也可以选择不修改。并且每个元素的操作是独立的。k是一个全局参数定义了每个元素允许修改的幅度。6. 进阶思考与变式题目理解了「最小差值 I」的本质后我们可以思考一些相关的变式问题以巩固这种数学思维。6.1 变式最小差值 II (Leetcode 910)这是第908题的强化版Leetcode 910题。题目变为 对于每个整数nums[i]我们可以选择将其变为nums[i] k或nums[i] - k。 目标是同样使得修改后数组的极差最小。区别在“最小差值 I”中元素可以变为区间内的任意值在“最小差值 II”中元素只有两种选择加k或减k。这大大增加了难度因为无法通过“微调”让所有值汇聚到一点。解决它通常需要排序和枚举分割点的思路时间复杂度为 O(n log n)。建议在掌握本题后挑战。6.2 思维扩展如何证明公式的正确性我们可以更形式化地证明max(0, max_val - min_val - 2*k)是最优解。下界Lower Bound无论我们如何修改新的最大值new_max至少是max_val - k因为最大值最多减k新的最小值new_min至多是min_val k因为最小值最多加k。因此极差new_max - new_min至少是(max_val - k) - (min_val k) max_val - min_val - 2k。又因为极差非负所以最小可能差值是max(0, max_val - min_val - 2k)。可达性Achievability我们可以构造一个修改方案来达到这个下界。如果max_val - min_val - 2k 0我们可以让所有元素都修改为同一个值例如(max_val min_val) / 2的附近整数只要落在每个元素的允许区间内即可使极差为0。如果max_val - min_val - 2k 0我们可以将最大值改为max_val - k最小值改为min_val k其他元素在其区间内任意选择例如保持不变即可达到极差max_val - min_val - 2k。 这就证明了我们找到的下界是可以达到的因此它就是最优解。7. 在力扣上的提交与优化7.1 直接提交将我们实现的Solution类代码复制到力扣的代码编辑器中点击提交通常可以轻松通过所有测试用例并且时间复杂度和空间复杂度都是最优的。7.2 一行代码版本Pythonic写法Python的简洁性允许我们将代码写得非常短但这可能会牺牲一些可读性。仅供欣赏和参考class Solution: def smallestRangeI(self, nums: List[int], k: int) - int: return max(0, max(nums) - min(nums) - 2 * k)点评虽然极其简洁但在面试或团队协作中更推荐使用带有清晰变量名和注释的版本便于他人理解和维护。7.3 一次遍历求极值我们之前的代码调用了两次内置函数max()和min()理论上Python可能会遍历数组两次。我们可以手动实现一次遍历同时找到最大值和最小值这在某些对常数项要求极高的场景下可能略有优势但对于此题内置函数已经足够高效且代码更清晰。class Solution: def smallestRangeI(self, nums: List[int], k: int) - int: min_val float(inf) max_val float(-inf) for num in nums: if num min_val: min_val num if num max_val: max_val num return max(0, max_val - min_val - 2 * k)8. 总结与刷题建议力扣第908题「最小差值 I」是一道优秀的数学思维题。它教会我们面对算法问题时不要急于编码而应先深入分析问题本质寻找数学规律或简化模型。回顾核心要点问题转化将“为每个元素选择修改值”的复杂问题转化为对数组原始最大值和最小值的调整问题。关键公式最小差值 max(0, (原始最大值 - 原始最小值) - 2 * k)。核心逻辑努力提升最小值降低最大值。如果它们调整后的范围有交集差值为0否则差值即为调整后范围之间的距离。刷题建议举一反三解决此题后立即去尝试它的进阶版「最小差值 II」Leetcode 910体会条件变化如何导致解法完全不同。归类总结将此类问题归类为“极值/范围调整”问题。类似的题目还有一些贪心或数学问题其核心都是通过分析边界条件来得到最优解。复杂度意识即使像本题这样输入规模可能不大也要养成寻找最优时间、空间复杂度解法的习惯。测试驱动编写代码时像第4节那样自己设计测试用例覆盖边界情况空数组本题不存在、单元素、k0、k极大等情况能极大提高代码正确率和一次通过率。掌握这道题不仅仅是解决了一个具体的算法问题更是获得了一种重要的解题思维从最极端的元素入手分析它们的变化范围从而推导出全局最优解。这种思维在解决许多优化问题时都非常有用。希望这篇详细的解析能帮助你彻底理解此题并在未来的刷题道路上更加顺利。