?LeetCode刷題實戰(zhàn)164：最大間距
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
題意
示例?1:
輸入: [3,6,9,1]
輸出: 3
解釋: 排序后的數(shù)組是 [1,3,6,9], 其中相鄰元素 (3,6) 和 (6,9) 之間都存在最大差值 3。
示例?2:
輸入: [10]
輸出: 0
解釋: 數(shù)組元素個數(shù)小于 2，因此返回 0。
說明:
你可以假設(shè)數(shù)組中所有元素都是非負整數(shù)，且數(shù)值在 32 位有符號整數(shù)范圍內(nèi)。
請嘗試在線性時間復(fù)雜度和空間復(fù)雜度的條件下解決此問題。
解題
思路:
class Solution:
????def maximumGap(self, nums:?List[int]) -> int:
????????n = len(nums)
????????if?n < 2: return?0
????????res?= 0
????????nums.sort()
????????for?i in range(1, n):
????????????res?= max(res, nums[i] - nums[i - 1])
????????return?res
n?是數(shù)組的個數(shù)。[1, 2, 5], 利用上式得?1，那必然不能組成以上數(shù)組！gap放在一個桶里，那么最大間隔一定在相互桶之間產(chǎn)生！num?在哪個桶里（換句話說，離min_num有幾個gap）。我們比如數(shù)組為?[1, 2, 3, 4，7],我們排除最大值和最小值， 把其他數(shù)組放入桶中，如下圖：| | | |
|2，3 | | 4 |
|_ _ _| | _ _ _|
class Solution:
????def maximumGap(self, nums:?List[int]) -> int:
????????n = len(nums)
????????if?n < 2: return?0
????????max_num = max(nums)
????????min_num = min(nums)
????????gap = math.ceil((max_num - min_num)/(n - 1))
????????bucket = [[float("inf"), float("-inf")] for?_ in range(n - 1)]
????????#print(bucket)
????????# 求出每個桶的最大值，和最小值
????????for?num in nums:
????????????if?num == max_num or?num == min_num:
????????????????continue
????????????loc?= (num - min_num) // gap
????????????bucket[loc][0] = min(num, bucket[loc][0])
????????????bucket[loc][1] = max(num, bucket[loc][1])
????????##print(bucket)
????????# 遍歷整個桶
????????preMin = min_num
????????res?= float("-inf")
????????for?x, y?in bucket:
????????????if?x?== float("inf") :
????????????????continue
????????????res?= max(res, x?- preMin)
????????????preMin = y
????????res?= max(res, max_num - preMin)
????????return?res