164. Maximum Gap
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.
Example 1:
Input: [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0.
Note:
- You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
- Try to solve it in linear time/space.
思路：
找出未排序数组排序后的最大间隔，一般如果是线性的时间复杂度，首先想到桶排序。
代码：
java：
代码语言：javascript复制class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if(n < 2) return 0;
int min = nums[0];
int max = nums[0];
for(int i = 1;i < n;i ){
if(min > nums[i]) min = nums[i];
if(max < nums[i]) max = nums[i];
}
int gap = (max-min)/(n-1);
if(gap == 0) gap ;
int len = (max-min)/gap 1;
int [] tmax = new int [len];
int [] tmin = new int [len];
for(int i = 0;i < n;i ){
int index = (nums[i]-min)/gap;
if(nums[i] > tmax[index]) tmax[index] = nums[i];
if(tmin[index] == 0 || nums[i] < tmin[index]) tmin[index] = nums[i];
}
int myMax = 0;
for(int i = 0;i < len;i ){
if(myMax < tmin[i]-min) myMax = tmin[i]-min;
if(tmax[i] != 0) min = tmax[i];
}
return myMax;
}
}
