Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Example :
Input : [1, 10, 5]
Output : 5
Return 0 if the array contains less than 2 elements.
You may assume that all the elements in the array are non-negative integers and fit in the 32-bit signed integer range.
You may also assume that the difference will not overflow.
思路:
Maximum Gap的最大可能值是max - min，最小可能值是gap = (max - min) / (n - 1)（比如[1, 2, 3]）。所以我们可以说maximum gap的取值范围是[gap, max - min] 我们可以依此将数组分配到如下的 n -1 个buckets [min, min + gap), [min + gap, min + 2 * gap), ...[min + (n - 1) * gap, mint + n * gap) 我们只需要记录每个bucket中的最小值和最大值，由于每个bucket中最大的差值是gap，小于maximum gap的可能值，所以我们需要找临近bucket中当前最小值减去之前bucket最大值中最大的。
Solution:
Time: O(n) Space: O(n)
public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int maximumGap(final List<Integer> A) {
int n = A.size();
int maximumGap = 0;
if (n < 2) return maximumGap;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i ++) {
int curr = A.get(i);
min = Math.min(min, curr);
max = Math.max(max, curr);
}
float gap = (float) (max - min) / (float) (n - 1);
int[][] buckets = new int[n - 1][2];
for (int i = 0; i < n - 1; i ++) {
buckets[i][0] = Integer.MAX_VALUE;
buckets[i][1] = Integer.MIN_VALUE;
}
for (int i = 0; i < n; i ++) {
int curr = A.get(i);
if (curr == max) continue;
int bucket = (int) (Math.floor((curr - min) / gap));
buckets[bucket][0] = Math.min(curr, buckets[bucket][0]);
buckets[bucket][1] = Math.max(curr, buckets[bucket][1]);
}
int prevMax = Integer.MIN_VALUE;
for (int i = 0 ; i < n - 1; i ++) {
int currMin = buckets[i][0];
if (currMin != Integer.MAX_VALUE && prevMax != Integer.MIN_VALUE) {
maximumGap = Math.max(maximumGap, currMin - prevMax);
}
if (buckets[i][1] != Integer.MIN_VALUE) {
prevMax = buckets[i][1];
}
}
maximumGap = Math.max(maximumGap, max - prevMax);
return maximumGap;
}
}