题目
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
要求：时间复杂度O(n).
示例
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
题干
排序之后
相邻元素之间最大的差值
时间和空间复杂度O(n)
思路
数组空间解法
找出数组中的最大值和最小值 最大值-最小珠+1 = 新数组的长度
然后循环旧数组 将旧数组的值-最小值 作为下标 旧数组的值作为值 赋值给新数组
循环一遍这样我们的新数组就具备以下特性
1。数组中元素是有序的
2。数组中在旧数组不存在的值为0
这样我们就可以遍历新数组 如果下一个值为0 即为间隙 divider++ 如果不为0 divider=1重置
选取maxdivider即可
排序解法
题目中要求时间和空间复杂度为线性 那么从排序的角度出发 哪些排序算法是线性的
能不能以此作为突破口
基数排序
时间复杂度为 O (nlog(r)m) 其中r为所采取的基数，而m为堆数
在良好的条件下是可以达到O(n)的复杂度
基数排序有两种LSD（Least Significant Digit first)） MSD（Most Significant Digit first）
一种为低位排序 一种为高位排序
例子 比如lsd 将个位按0～9分组 接着十位 0～9分组 直到最高位链接后有序
字典树算法
解答
数组空间解法
class Solution {
public int maximumGap(int[] nums) {
if(nums.length<2){
return 0;
}
int max = findMax(nums);
int min = findMin(nums);
int size = max-min+1;//数组池的长度
System.out.println("大小:"+size);
int[] container = new int[size];
for(int i=0;i<nums.length;i++){
container[nums[i]-min]=nums[i];
}
System.out.println("");
int maxDivider = 0;
int divider = 1;
for(int i=0;i<container.length;i++){
if(container[i]==0){
divider++;
if(divider>maxDivider){
maxDivider = divider;
}
}else {
divider=1;
}
}
return maxDivider;
}
public static int findMax(int[] arr){
int max = arr[0];
for(int num:arr){
if(num>max){
max = num;
}
}
return max;
}
public static int findMin(int[] arr){
int min = arr[0];
for(int num:arr){
if(num<min){
min = num;
}
}
return min;
}
}
时空复杂度分析
如果采用数组空间解法 时间复杂度为O(n) 空间复杂度我理解是为O(n)但是运行在leetcode超出内存限制 故而需要找到更好的方法
结语
此题难度较高 体现在时间复杂度上 线性要求
