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
透過蝦皮分潤計畫,輕鬆賺取零用金!本文分享5-6月實測心得,包含數據流程、實際收入、平臺優點及注意事項,並推薦高分潤商品,教你如何運用空閒時間創造被動收入。
Thumbnail
透過蝦皮分潤計畫,輕鬆賺取零用金!本文分享5-6月實測心得,包含數據流程、實際收入、平臺優點及注意事項,並推薦高分潤商品,教你如何運用空閒時間創造被動收入。
Thumbnail
單身的人有些會養寵物,而我養植物。畢竟寵物離世會傷心,植物沒養好再接再厲就好了~(笑)
Thumbnail
單身的人有些會養寵物,而我養植物。畢竟寵物離世會傷心,植物沒養好再接再厲就好了~(笑)
Thumbnail
不知你有沒有過這種經驗?衛生紙只剩最後一包、洗衣精倒不出來,或電池突然沒電。這次一次補貨,從電池、衛生紙到洗衣精,還順便分享使用心得。更棒的是,搭配蝦皮分潤計畫,愛用品不僅自己用得安心,分享給朋友還能賺回饋。立即使用推薦碼 X5Q344E,輕鬆上手,隨時隨地賺取分潤!
Thumbnail
不知你有沒有過這種經驗?衛生紙只剩最後一包、洗衣精倒不出來,或電池突然沒電。這次一次補貨,從電池、衛生紙到洗衣精,還順便分享使用心得。更棒的是,搭配蝦皮分潤計畫,愛用品不僅自己用得安心,分享給朋友還能賺回饋。立即使用推薦碼 X5Q344E,輕鬆上手,隨時隨地賺取分潤!
Thumbnail
身為一個典型的社畜,上班時間被會議、進度、KPI 塞得滿滿,下班後只想要找一個能夠安靜喘口氣的小角落。對我來說,畫畫就是那個屬於自己的小樹洞。無論是胡亂塗鴉,還是慢慢描繪喜歡的插畫人物,那個專注在筆觸和色彩的過程,就像在幫心靈按摩一樣,讓緊繃的神經慢慢鬆開。
Thumbnail
身為一個典型的社畜,上班時間被會議、進度、KPI 塞得滿滿,下班後只想要找一個能夠安靜喘口氣的小角落。對我來說,畫畫就是那個屬於自己的小樹洞。無論是胡亂塗鴉,還是慢慢描繪喜歡的插畫人物,那個專注在筆觸和色彩的過程,就像在幫心靈按摩一樣,讓緊繃的神經慢慢鬆開。
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