LeetCode 164. 最大间距 (桶排序)

本文主要是介绍LeetCode 164. 最大间距 (桶排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1:输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-gap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution

思路解析
在这里插入图片描述

class Solution:def maximumGap(self, nums: List[int]) -> int:if not nums or len(nums) < 2: return 0max_ = max(nums)min_ = min(nums)max_gap = 0each_bucket_len = max(1,(max_-min_) // (len(nums)-1))buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]for i in range(len(nums)):loc = (nums[i] - min_) // each_bucket_lenbuckets[loc].append(nums[i])prev_max = float('inf')for i in range(len(buckets)):if buckets[i] and prev_max != float('inf'):max_gap = max(max_gap, min(buckets[i])-prev_max)if buckets[i]:prev_max = max(buckets[i])return max_gap# 作者：yanghk
# 链接：https://leetcode-cn.com/problems/maximum-gap/solution/python3-tong-pai-xu-by-yanghk/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。