给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。看到数组元素全部为非负整数以及线性时间复杂度的排序就想到了桶排序。桶排序简单来说就是把元素根据大小在一次遍历中放到对应的桶中。之后将每个桶中的元素依次取出组成排序后的数组。可参考桶排序（箱排序）原理及其时间复杂度详解中的图解：
但桶排序的问题也较为明显：在资源分布不均匀时会占用大量的空间，他的空间复杂度是O(m)，其中m位桶的个数。
所以在此题中，我们能不能直接通过桶排序并计算最大的连续空桶数呢？代码如下：
def maximumGap(self, nums) -> int: if len(nums)<2: return 0 # 初始化桶，桶的个数为数组中最大值 buckets = [0]*(max(nums)+1) # 把数字放入对应的桶中 for num in nums: buckets[num]+=1 gap:int = 0 max_gap:int = 0 init = False # 遍历桶并数出最大连续空桶的数量 for bucket in buckets: gap+=1 if bucket>0: if not init: init = True elif gap > max_gap: max_gap = gap gap = 0 return max_gap这个很莽的算法时间复杂度为O(m+n)，空间复杂度为O(m)。（你就说是不是线性复杂度吧）
提交后果不其然在[2,9999999]的用例上超时了。
要优化这个算法，我们就需要考虑在一个桶中放多个元素，可是如果知识单纯的扩大桶的容量，我们还是需要在每个桶中进行排序，无法降低时间复杂度到线性。看了看LeetCode的讨论贴后，发现引入鸽笼原则（或者叫抽屉原则）可以解决这个问题，这个原则很简单也很符合常识：
在N个鸽笼中放N-m个鸽子，则至少有m个鸽笼是空的。
在N个鸽笼中放大于N个各自，则至少有一个鸽笼中有多个鸽子。
具体到本例中，我们把N个数在桶排序时放入N+1个桶，则会产生至少1个空桶。而由于所有桶的大小是一致的，所以最大间隔一定是在一个或多个连续的空桶左右产生的。例如，我们在处理数组[1,2,10,9]时，我们需要将[1,10]这个区间均匀的分割为N+1，也就是5个区间，区间大小为(10-1)//5+1=2,如下：
[1,3) [3,5) [5,7) [7,9) [9,11)这里为了包含最大值，需要为整除后的值+1。之后我们把这四个数放入如上五个桶中：
[[1,2],[],[],[],[9,10]可以看到中间产生了3个空桶，我们只需计算每段空桶前后两个桶中前桶的最大值与后桶的最小值便可知道一个可能为最大间距的值。得到所有空桶左右的间距后取最大间距，就是我们最终需要的答案。
