题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
|
题解
要求最大间距，常规方法就是对数组进行排序，然后遍历计算相邻元素的间距大小，最后得出结果；但是对于本题来说，题目限制了空间以及时间复杂度为线性级别，因此，常规方法就行不通了。
桶排序——O(N)时间复杂度级别的排序算法是AC本题的一个关键，另一个关键就是抽屉原理。几个关键步骤如下
- 找出数组的最大元素与最小元素——O(N)时间复杂度
- 创建三个数组，大小为数组元素个数+1，第一个数组作为桶排序的数组，第二个数组记录每个桶的装的元素的最小值，第三个数组记录每个桶装的元素的最大值
- 除了最小元素与最大元素在第一个桶与最后一个桶之外，将剩下的(n - 2)个元素放入(n - 1)个桶中，那么由抽屉原理可知，必然有一个桶是空的，而这个空桶左边第一个有元素的桶的最大元素与空桶右边第一个有元素的桶的最小元素的差值，就是所求的最大间距
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution:
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return 0
if len(nums) == 2:
return abs(nums[0] - nums[1])
return self.getMaxGap(arr=nums, n=len(nums))
def getMaxGap(self, arr, n):
maxN, minN = self.get_max_min(arr=arr)
count = [0 for i in range(n + 1)]
low = [maxN for i in range(n + 1)]
heigh = [minN for i in range(n + 1)]
for i in range(1, n + 1):
bucket = int((n - 1) * (arr[i - 1] - minN) / (maxN - minN)) + 1
if bucket == n:
bucket -= 1
count[bucket] += 1
low[bucket] = min(low[bucket], arr[i - 1])
heigh[bucket] = max(heigh[bucket], arr[i - 1])
maxGap = 0; l = heigh[1]
for i in range(2, n):
if count[i]:
maxGap = max(maxGap, low[i] - l)
l = heigh[i]
return maxGap
def get_max_min(self, arr):
a = -1; b = 2 ** 32
for i in range(len(arr)):
a = max(a, arr[i])
b = min(b, arr[i])
return a, b
|