算法——乱序数组排序后的元素最大间距值

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
leetcode

解题思路：如果进行排序，这里会超时。采用桶排序的思想，可以在线性时间解决。

1. 首先建立桶，每个桶中只需要存放这个桶中元素的最大值和最小值。
2. 桶尺寸就是数组中元素范围再除以数组的大小，桶的数量就是数组范围除以桶的尺寸再加一。
   为什么需要这样规定桶的尺寸呢？因为这样可以让最大的间距的两个元素在两个不同的桶中。可以证明一下，因为我们用元素范围之差除以元素个数，所以桶的尺寸就是平均的元素间距，显然最大间距最大的元素不可能在同一个桶。
   为什么要最大间距的元素在两个不同的桶中呢？如果两个元素在桶中，那就又需要再桶中进行排序求解了，这样桶排序的优势就没了。
3. 遍历数组，把元素放到桶中。这里只需要一个桶中元素的最大值和最小值，因为答案不会在一个桶中，所以，只需要比较相邻桶的边界就能获取答案，其余的值只会碍事。
4. 遍历桶，用当前桶的最小值减去上一个桶的最大值，就是可能的答案。

class Bucket {
    public boolean isUsed = false;
    public int min = Integer.MAX_VALUE;
    public int max = Integer.MIN_VALUE;

}
class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if(n <= 1) return 0;

        int maxn = nums[0], minn = nums[0];

		// 求元素范围
        for(int num : nums) {
            maxn = Math.max(maxn, num);
            minn = Math.min(minn, num);
        }
	
		// 计算桶的大小和数量
        int size = Math.max(1, (maxn - minn) / (n - 1));
        int bucketNum = (maxn - minn) / size + 1;

        List<Bucket> buckets = new ArrayList<>();

        for(int i = 0; i < bucketNum; i++) buckets.add(new Bucket());

	    // 把元素放到桶里，只取桶中的最大值和最小值
        for(int num : nums) {
            int i = (num - minn) / size;
            buckets.get(i).isUsed = true;
            buckets.get(i).min = Math.min(buckets.get(i).min, num);
            buckets.get(i).max = Math.max(buckets.get(i).max, num);
        }

        int pre = minn, res = 0;
		// 遍历桶，获取最大间距
        for(Bucket b : buckets) {
            if(!b.isUsed) continue;
            res = Math.max(res, b.min - pre);
            pre = b.max;
        }

        return res;
    }
}