在算法刷題的過程中我們常常會遇到一類看似簡單實(shí)則暗藏數(shù)學(xué)巧思的題目。力扣LeetCode第908題「最小差值 I」就是其中的典型代表。很多同學(xué)初次看到題目描述時可能會覺得一頭霧水或者嘗試用復(fù)雜的排序、遍歷去解決結(jié)果要么超時要么代碼冗長。本文將為你徹底拆解這道題揭示其背后的數(shù)學(xué)本質(zhì)并提供清晰、高效的Python解決方案。無論你是正在準(zhǔn)備面試的求職者還是希望提升算法思維的學(xué)生掌握這道題的解法都能讓你對“極值”和“范圍”類問題有更深的理解。1. 問題背景與核心概念1.1 問題描述與官方鏈接力扣第908題「最小差值 I」的官方描述如下 給你一個整數(shù)數(shù)組nums和一個整數(shù)k。 對于數(shù)組中的每個下標(biāo)i0 i nums.length我們可以將nums[i]的值修改為范圍在[nums[i] - k, nums[i] k]內(nèi)的任意整數(shù)。該操作最多只能進(jìn)行一次。 我們的目標(biāo)是通過修改或不修改數(shù)組中的每個元素使得修改后數(shù)組的“最大值”與“最小值”之間的差值最小化。 請你返回在執(zhí)行上述操作后數(shù)組可能的最小差值。示例 1輸入nums [1], k 0 輸出0 解釋數(shù)組只有一個元素最大值和最小值都是1差值為0。示例 2輸入nums [0, 10], k 2 輸出6 解釋可以將數(shù)組修改為 [2, 8]。最大值8與最小值2的差值為6。示例 3輸入nums [1, 3, 6], k 3 輸出0 解釋可以將數(shù)組修改為 [3, 3, 3]。最大值和最小值相等差值為0。1.2 核心概念什么是“最小差值”這道題的核心在于理解“操作”的實(shí)質(zhì)。題目允許我們對數(shù)組中的每一個元素獨(dú)立地進(jìn)行一次調(diào)整調(diào)整的范圍是以該元素原始值為中心上下浮動k個單位。這意味著對于任意一個元素nums[i]其最終可能的值是一個區(qū)間[nums[i] - k, nums[i] k]。我們的目標(biāo)是通過為每個元素在這個區(qū)間內(nèi)選擇一個最終值使得整個數(shù)組的最大值與最小值的差盡可能小。這聽起來像是一個復(fù)雜的組合優(yōu)化問題但如果我們深入思考其數(shù)學(xué)本質(zhì)會發(fā)現(xiàn)一個非常簡潔的規(guī)律。1.3 為什么這道題值得學(xué)習(xí)思維轉(zhuǎn)換它訓(xùn)練你將一個看似需要遍歷所有可能性的問題轉(zhuǎn)化為一個基于極值的數(shù)學(xué)計(jì)算問題。理解極值深刻理解數(shù)組的“最大值”和“最小值”在允許波動下的行為。面試高頻這類考察數(shù)學(xué)思維和問題簡化能力的題目在筆試和面試中非常常見。代碼簡潔最優(yōu)解法通常只需要幾行代碼是體現(xiàn)算法功力的好題目。2. 解題思路分析與數(shù)學(xué)推導(dǎo)直接對每個元素進(jìn)行枚舉修改顯然是不現(xiàn)實(shí)的。我們需要找到問題的關(guān)鍵。2.1 思路啟發(fā)考慮兩個極端情況讓我們先考慮數(shù)組中的兩個特殊元素原始數(shù)組的最大值max_num和最小值min_num。對于最小值min_num我們最多能將它增加k變?yōu)閙in_num k。對于最大值max_num我們最多能將它減少k變?yōu)閙ax_num - k。我們的核心目標(biāo)是縮小max_num和min_num之間的距離。2.2 數(shù)學(xué)推導(dǎo)與核心公式設(shè)原始數(shù)組的最大值為max_val最小值為min_val。在允許修改的情況下可能的最小值是多少最小值min_val最多只能增加到min_val k。因此整個數(shù)組修改后可能的最小值new_min至少是min_val但我們可以嘗試讓它變大最大不會超過min_val k。實(shí)際上new_min可以是min_val到min_val k之間的任意值但為了縮小與最大值的差距我們通常希望new_min盡可能大。同理可能的最大值是多少最大值max_val最多只能減少到max_val - k。因此整個數(shù)組修改后可能的最大值new_max至多是max_val但我們可以嘗試讓它變小最小不會低于max_val - k。為了縮小差距我們通常希望new_max盡可能小。那么最優(yōu)策略是什么我們努力讓最小值變大讓最大值變小。如果它們調(diào)整后的范圍有重疊我們甚至可以讓它們相等調(diào)整后的最小值范圍[min_val, min_val k]調(diào)整后的最大值范圍[max_val - k, max_val]如果(min_val k) (max_val - k)說明這兩個區(qū)間有重疊。我們完全可以選擇一個值讓它同時落在兩個區(qū)間內(nèi)從而使new_min等于new_max。此時最小差值就是0。如果(min_val k) (max_val - k)說明無論我們怎么調(diào)整最小值能到達(dá)的最高點(diǎn)仍然低于最大值能到達(dá)的最低點(diǎn)。它們之間始終存在一個“無法跨越的鴻溝”。此時我們最優(yōu)的做法是將最小值提升到最高 (min_val k)將最大值降低到最低 (max_val - k)。此時的最小差值就是(max_val - k) - (min_val k) max_val - min_val - 2 * k。綜上所述最小差值的計(jì)算公式為max(0, (max_val - min_val) - 2 * k)這個max(0, ...)確保了當(dāng)差值可能為負(fù)數(shù)時即區(qū)間重疊時我們?nèi)?。2.3 思路驗(yàn)證用之前的例子驗(yàn)證示例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. 環(huán)境準(zhǔn)備與代碼實(shí)現(xiàn)3.1 環(huán)境說明編程語言Python 3.x。本題解不依賴任何第三方庫使用Python內(nèi)置函數(shù)即可。代碼編輯器/IDE任意你熟悉的工具即可如 VS Code, PyCharm, Jupyter Notebook。力扣刷題環(huán)境你可以在力扣官網(wǎng)直接使用其在線編輯器。3.2 核心函數(shù)實(shí)現(xiàn)根據(jù)上述推導(dǎo)代碼實(shí)現(xiàn)極其簡潔。我們只需要找到數(shù)組的最大值和最小值然后套用公式即可。class Solution: def smallestRangeI(self, nums: List[int], k: int) - int: 計(jì)算執(zhí)行操作后數(shù)組可能的最小差值。 參數(shù): nums (List[int]): 輸入的整數(shù)數(shù)組。 k (int): 允許每個元素調(diào)整的最大幅度。 返回: int: 可能的最小差值。 # 步驟1: 找到數(shù)組中的最大值和最小值 max_val max(nums) min_val min(nums) # 步驟2: 應(yīng)用核心公式計(jì)算最小差值 # 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:這是力扣題目要求的函數(shù)簽名包含類型注解清晰明了。max_val max(nums)和min_val min(nums)使用Python內(nèi)置的max()和min()函數(shù)以O(shè)(n)的時間復(fù)雜度遍歷數(shù)組一次實(shí)際上max()和min()各遍歷一次總體仍是 O(n)找到極值。這是效率最高的方法。result max(0, (max_val - min_val) - 2 * k)這是算法的核心。max_val - min_val計(jì)算原始數(shù)組的極差。減去2 * k表示我們試圖通過調(diào)整將極差縮小2k最小值加k最大值減k。max(0, ...)確保結(jié)果非負(fù)。如果計(jì)算出的差值為負(fù)說明極差可以完全消除最小差值就是0。return result返回計(jì)算結(jié)果。3.4 復(fù)雜度分析時間復(fù)雜度O(n)。其中 n 是數(shù)組nums的長度。我們只需要遍歷數(shù)組兩次分別求最大值和最小值或者一些優(yōu)化實(shí)現(xiàn)可以一次遍歷同時找到最大最小值但復(fù)雜度仍是 O(n)?？臻g復(fù)雜度O(1)。我們只使用了常數(shù)級別的額外空間幾個變量與輸入數(shù)組的大小無關(guān)。4. 測試用例與運(yùn)行驗(yàn)證為了確保代碼的正確性我們需要設(shè)計(jì)多種邊界情況和典型場景進(jìn)行測試。# 測試代碼 def test_smallestRangeI(): solution Solution() # 測試用例1: 單元素數(shù)組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所有測試用例通過) # 運(yùn)行測試 if __name__ __main__: # 注意需要將上面的Solution類定義包含進(jìn)來 test_smallestRangeI()將上述測試代碼與Solution類放在同一個文件中運(yùn)行你會看到所有測試通過的輸出。這驗(yàn)證了我們算法邏輯的正確性。5. 常見錯誤與思維誤區(qū)在解決這道題時初學(xué)者容易陷入以下幾個誤區(qū)5.1 誤區(qū)一嘗試修改所有元素的值錯誤想法“我需要為每個nums[i]決定一個具體的修改值然后計(jì)算新數(shù)組的極差再找最小值?！狈治鲞@種思路會導(dǎo)致組合爆炸。數(shù)組有n個元素每個元素有(2k1)種可能如果k小搜索空間巨大。題目并沒有要求輸出具體的修改方案只要求最小差值因此這是一個典型的優(yōu)化問題往往存在數(shù)學(xué)規(guī)律無需枚舉。5.2 誤區(qū)二只關(guān)注最大值和最小值但策略錯誤錯誤想法“我把最大值減小k最小值增加k然后計(jì)算新差值(max-k) - (mink)就行了。”分析這個想法接近了但忽略了關(guān)鍵情況——當(dāng)(max - k)可能小于(min k)時計(jì)算出的差值會是負(fù)數(shù)這在實(shí)際的差值中是沒有意義的。差值最小就是0。因此必須用max(0, ...)來保證結(jié)果的正確性。這是本題最易錯的點(diǎn)。5.3 誤區(qū)三使用排序錯誤代碼示例def smallestRangeI_wrong(nums, k): nums.sort() # 不必要的排序O(n log n) 復(fù)雜度 return max(0, (nums[-1] - nums[0]) - 2*k)分析雖然這段代碼能得到正確結(jié)果但其時間復(fù)雜度是O(n log n)因?yàn)榕判虿僮?。而通過max()和min()函數(shù)只需要O(n)的時間。在算法題中應(yīng)選擇最優(yōu)解法。排序在這里是多余且低效的。5.4 誤區(qū)四誤解“最多進(jìn)行一次操作”錯誤理解認(rèn)為整個數(shù)組只能修改一次或者每個元素只能被修改一次但必須選擇同一個k值。正確理解題目意思是對于每個下標(biāo) i你可以選擇對 nums[i] 進(jìn)行一次修改操作修改到其允許的范圍內(nèi)也可以選擇不修改。并且每個元素的操作是獨(dú)立的。k是一個全局參數(shù)定義了每個元素允許修改的幅度。6. 進(jìn)階思考與變式題目理解了「最小差值 I」的本質(zhì)后我們可以思考一些相關(guān)的變式問題以鞏固這種數(shù)學(xué)思維。6.1 變式最小差值 II (Leetcode 910)這是第908題的強(qiáng)化版Leetcode 910題。題目變?yōu)?對于每個整數(shù)nums[i]我們可以選擇將其變?yōu)閚ums[i] k或nums[i] - k。 目標(biāo)是同樣使得修改后數(shù)組的極差最小。區(qū)別在“最小差值 I”中元素可以變?yōu)閰^(qū)間內(nèi)的任意值在“最小差值 II”中元素只有兩種選擇加k或減k。這大大增加了難度因?yàn)闊o法通過“微調(diào)”讓所有值匯聚到一點(diǎn)。解決它通常需要排序和枚舉分割點(diǎn)的思路時間復(fù)雜度為 O(n log n)。建議在掌握本題后挑戰(zhàn)。6.2 思維擴(kuò)展如何證明公式的正確性我們可以更形式化地證明max(0, max_val - min_val - 2*k)是最優(yōu)解。下界Lower Bound無論我們?nèi)绾涡薷男碌淖畲笾祅ew_max至少是max_val - k因?yàn)樽畲笾底疃鄿pk新的最小值new_min至多是min_val k因?yàn)樽钚≈底疃嗉觡。因此極差new_max - new_min至少是(max_val - k) - (min_val k) max_val - min_val - 2k。又因?yàn)闃O差非負(fù)所以最小可能差值是max(0, max_val - min_val - 2k)?？蛇_(dá)性Achievability我們可以構(gòu)造一個修改方案來達(dá)到這個下界。如果max_val - min_val - 2k 0我們可以讓所有元素都修改為同一個值例如(max_val min_val) / 2的附近整數(shù)只要落在每個元素的允許區(qū)間內(nèi)即可使極差為0。如果max_val - min_val - 2k 0我們可以將最大值改為max_val - k最小值改為min_val k其他元素在其區(qū)間內(nèi)任意選擇例如保持不變即可達(dá)到極差max_val - min_val - 2k。 這就證明了我們找到的下界是可以達(dá)到的因此它就是最優(yōu)解。7. 在力扣上的提交與優(yōu)化7.1 直接提交將我們實(shí)現(xiàn)的Solution類代碼復(fù)制到力扣的代碼編輯器中點(diǎn)擊提交通?？梢暂p松通過所有測試用例并且時間復(fù)雜度和空間復(fù)雜度都是最優(yōu)的。7.2 一行代碼版本Pythonic寫法Python的簡潔性允許我們將代碼寫得非常短但這可能會犧牲一些可讀性。僅供欣賞和參考class Solution: def smallestRangeI(self, nums: List[int], k: int) - int: return max(0, max(nums) - min(nums) - 2 * k)點(diǎn)評雖然極其簡潔但在面試或團(tuán)隊(duì)協(xié)作中更推薦使用帶有清晰變量名和注釋的版本便于他人理解和維護(hù)。7.3 一次遍歷求極值我們之前的代碼調(diào)用了兩次內(nèi)置函數(shù)max()和min()理論上Python可能會遍歷數(shù)組兩次。我們可以手動實(shí)現(xiàn)一次遍歷同時找到最大值和最小值這在某些對常數(shù)項(xiàng)要求極高的場景下可能略有優(yōu)勢但對于此題內(nèi)置函數(shù)已經(jīng)足夠高效且代碼更清晰。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. 總結(jié)與刷題建議力扣第908題「最小差值 I」是一道優(yōu)秀的數(shù)學(xué)思維題。它教會我們面對算法問題時不要急于編碼而應(yīng)先深入分析問題本質(zhì)尋找數(shù)學(xué)規(guī)律或簡化模型?；仡櫤诵囊c(diǎn)問題轉(zhuǎn)化將“為每個元素選擇修改值”的復(fù)雜問題轉(zhuǎn)化為對數(shù)組原始最大值和最小值的調(diào)整問題。關(guān)鍵公式最小差值 max(0, (原始最大值 - 原始最小值) - 2 * k)。核心邏輯努力提升最小值降低最大值。如果它們調(diào)整后的范圍有交集差值為0否則差值即為調(diào)整后范圍之間的距離。刷題建議舉一反三解決此題后立即去嘗試它的進(jìn)階版「最小差值 II」Leetcode 910體會條件變化如何導(dǎo)致解法完全不同。歸類總結(jié)將此類問題歸類為“極值/范圍調(diào)整”問題。類似的題目還有一些貪心或數(shù)學(xué)問題其核心都是通過分析邊界條件來得到最優(yōu)解。復(fù)雜度意識即使像本題這樣輸入規(guī)?？赡懿淮笠惨B(yǎng)成尋找最優(yōu)時間、空間復(fù)雜度解法的習(xí)慣。測試驅(qū)動編寫代碼時像第4節(jié)那樣自己設(shè)計(jì)測試用例覆蓋邊界情況空數(shù)組本題不存在、單元素、k0、k極大等情況能極大提高代碼正確率和一次通過率。掌握這道題不僅僅是解決了一個具體的算法問題更是獲得了一種重要的解題思維從最極端的元素入手分析它們的變化范圍從而推導(dǎo)出全局最優(yōu)解。這種思維在解決許多優(yōu)化問題時都非常有用。希望這篇詳細(xì)的解析能幫助你徹底理解此題并在未來的刷題道路上更加順利。