908. Smallest Range I (最小差值 I)

更新 發佈閱讀 1 分鐘


英文版點我中文版點我


↑看個小廣告,支持好內容↑



讀懂這段在表達啥,這題就算解掉一半了

讀懂這段在表達啥,這題就算解掉一半了

陣列中的每項都有一次調整的機會,可以被任意改成 nums[i]-k~nums[i]+k 之間的整數,而我們的目標是:盡可能縮小陣列的全距 (最大值-最小值)。


似乎很直觀,就把小的數字變大一點、大的數字變小一點就好了對吧?

// 成功的案例
nums=[1,9], k=2: 1397,全距=4

// 失敗的案例
nums=[5,7], k=3: 5874,全距=4
(顯然不對,這比調整前的差距還大)


事實上,直接把 5 改成 7,兩數就相同了,故正確答案應該是 0;即便我們在陣列加入很多很多 6,他們照樣可以被改成 7,並不影響結果。綜上,我們得到兩個結論:


  • 最小範圍確實是由 [max, min] 所決定。
  • 差值不會為負,當 max-min-2*k<0,答案必定為 0。


[備註] 這題因為文字敘述收到許多負評,但我認為它是刻意為之的,如何在有限時間內消化提取線索解題,也是邏輯與閱讀素養的一大考驗。話說回來,把蕪雜的需求化約進程式設計,這本身就是開發實務的縮影哪~ (茶


  • 本題分類標籤:ArrayMath
  • 本題正解率=69.3%

❤️ 若內容對你實用,歡迎追蹤本專題,或小額贊助支持~
⭐ 這是我的第 13 篇刷題筆記,完整解題索引看這裡 → Here

留言
avatar-img
留言分享你的想法!
avatar-img
LeetCode King
55會員
59內容數
我要成為 LeetCode 王!快跟我一起踏上旅程!
LeetCode King的其他內容
2024/06/25
看到題目問「種類」時,集合就是你最好的朋友。
Thumbnail
2024/06/25
看到題目問「種類」時,集合就是你最好的朋友。
Thumbnail
2023/11/13
究竟誰是 i、誰又是 j?矩陣問題務必趁腦子清楚時才解 XDD
Thumbnail
2023/11/13
究竟誰是 i、誰又是 j?矩陣問題務必趁腦子清楚時才解 XDD
Thumbnail
2023/10/17
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
Thumbnail
2023/10/17
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
Thumbnail
看更多
你可能也想看
Thumbnail
每次都很煩惱交換禮物要送什麼嗎?這次分享五款千元以下的質感好物,有香氛、海綿寶寶積木、質感可蒸可微波便當盒、吉卜力造型毛巾和實用包款,讓你輕鬆挑選聖誕節禮物💝
Thumbnail
每次都很煩惱交換禮物要送什麼嗎?這次分享五款千元以下的質感好物,有香氛、海綿寶寶積木、質感可蒸可微波便當盒、吉卜力造型毛巾和實用包款,讓你輕鬆挑選聖誕節禮物💝
Thumbnail
嗨大家!最近過得好嗎?我好久沒發文了!😀 正在進行一個月的歐洲旅行,這次橫跨三個國家,也發生不少有趣的事,接下來也會陸續整理發佈~ 今天想分享的是旅行中必備的好物,我也在旅途中親自進行實測, 希望透過這篇的購買清單,幫助到即將要規劃旅行的你:)
Thumbnail
嗨大家!最近過得好嗎?我好久沒發文了!😀 正在進行一個月的歐洲旅行,這次橫跨三個國家,也發生不少有趣的事,接下來也會陸續整理發佈~ 今天想分享的是旅行中必備的好物,我也在旅途中親自進行實測, 希望透過這篇的購買清單,幫助到即將要規劃旅行的你:)
Thumbnail
大家都知道要補充膠原蛋白,但步入中年後的我,肌膚的變化不只是「流失變快」,連狀態也開始慢慢改變。 後來才明白,原來膠原蛋白的補充不只要「吃對」,更要「吃對時間」。 就像肌膚保養會分成早晚程序,膠原的補充其實也需要「分時」進行,才能更貼近需求,效果也更好。 BEAUTY CLUB 讓我養成了「早
Thumbnail
大家都知道要補充膠原蛋白,但步入中年後的我,肌膚的變化不只是「流失變快」,連狀態也開始慢慢改變。 後來才明白,原來膠原蛋白的補充不只要「吃對」,更要「吃對時間」。 就像肌膚保養會分成早晚程序,膠原的補充其實也需要「分時」進行,才能更貼近需求,效果也更好。 BEAUTY CLUB 讓我養成了「早
Thumbnail
發現每天固定一個小動作,肌膚整體狀態真的會更穩定,照鏡子的心情也跟著好起來。 早上我習慣吃一包 TIMESEAL 早安膠原蛋白,粉末狀、很好入口,使用小分子技術,搭配維生素C與專利原料 ( 雙胜肽膠原、PANMOL® NADH)。對我來說,就是先把一天的彈潤感打好底,也讓整天狀態更有精神。 晚
Thumbnail
發現每天固定一個小動作,肌膚整體狀態真的會更穩定,照鏡子的心情也跟著好起來。 早上我習慣吃一包 TIMESEAL 早安膠原蛋白,粉末狀、很好入口,使用小分子技術,搭配維生素C與專利原料 ( 雙胜肽膠原、PANMOL® NADH)。對我來說,就是先把一天的彈潤感打好底,也讓整天狀態更有精神。 晚
Thumbnail
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
Thumbnail
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目的情境是設計並且實現一個包含所有正整數的數據流,以set集合的方式存在。 數據流 = {1, 2, 3, 4, ..., ∞} 要求我們去實現定義好的function介面: SmallestInfiniteSet()建構子,初始化這個包含所有正整數的數據流。 int po
Thumbnail
題目敘述 題目的情境是設計並且實現一個包含所有正整數的數據流,以set集合的方式存在。 數據流 = {1, 2, 3, 4, ..., ∞} 要求我們去實現定義好的function介面: SmallestInfiniteSet()建構子,初始化這個包含所有正整數的數據流。 int po
Thumbnail
題目 : 88. Merge Sorted Array
Thumbnail
題目 : 88. Merge Sorted Array
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News