Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

桶排序

复杂度

O(N) 时间 O(N) 空间

思路

假设有N个元素A到B。

那么最大差值一定大于floor[(B - A) / (N - 1)]，floor就是向下取整

令bucket（桶）的大小len = floor[(B - A) / (N - 1)]，则最多会有(B - A) / len + 1个桶

对于数组中的任意整数K，很容易通过算式loc = (K - A) / len找出其桶的位置，然后维护每一个桶的最大值和最小值

由于同一个桶内的元素之间的差值至多为len - 1，因此最终答案不会从同一个桶中选择。

对于每一个非空的桶p，找出下一个非空的桶q，则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。

注意

注意特殊情况

代码

主程序：

public int maximumGap(int[] nums) {    int n = nums.length;    if (n <= 1)        return 0;    int max = getMax(nums);    int min = getMin(nums);    int len = (max - min) / (n - 1);//桶长    if (len == 0)        return max - min;    int k = ((max - min) / len) + 1;//桶数    Bucket[] buckets = new Bucket[k];    init(buckets, min, len);    fill(buckets, nums, min, len);    int maxGap = find(buckets);    return maxGap;}

Utilities:

public int getMax(int[] nums) {    int max = Integer.MIN_VALUE;    for (int cur : nums)        max = Math.max(cur, max);    return max;}public int getMin(int[] nums) {    int min = Integer.MAX_VALUE;    for (int cur : nums)        min = Math.min(cur, min);    return min;}public int find(Bucket[] buckets) {    int premax = Integer.MIN_VALUE;    int curmin = Integer.MAX_VALUE;    int max = Integer.MIN_VALUE;    for (int i = 0; i < buckets.length; i++) {        if (buckets[i].min != Integer.MAX_VALUE)            curmin = buckets[i].min;        if (premax != Integer.MIN_VALUE && curmin != Integer.MAX_VALUE)            max = Math.max(curmin - premax, max);        if (buckets[i].max != Integer.MIN_VALUE)            premax = buckets[i].max;    }    return max;}public void fill(Bucket[] buckets, int[] nums, int min, int len) {    for (int cur : nums) {        int whichBucket = (cur - min) / len;        buckets[whichBucket].max = Math.max(buckets[whichBucket].max, cur);        buckets[whichBucket].min = Math.min(buckets[whichBucket].min, cur);    }}public void init(Bucket[] buckets, int min, int len) {    for (int i = 0; i < buckets.length; i++) {        buckets[i] = new Bucket(min, min + len - 1);        min = min + len;    }}

Bucket类:

class Bucket {    int left;//inclusive，其实这个是没必要的    int right;//inclusive，其实这个是没必要的    int max;    int min;    Bucket(int left, int right) {        this.left = left;        this.right = right;        this.max = Integer.MIN_VALUE;        this.min = Integer.MAX_VALUE;    }}