給定一個無序的數組，找出數組在排序之后，相鄰元素之間最大的差值。

如果數組元素個數小于 2，則返回 0。

示例 1:

輸入: [3,6,9,1]
輸出: 3
解釋: 排序后的數組是 [1,3,6,9], 其中相鄰元素 (3,6) 和 (6,9) 之間都存在最大差值 3。
示例 2:

輸入: [10]
輸出: 0
解釋: 數組元素個數小于 2，因此返回 0。
說明:

你可以假設數組中所有元素都是非負整數，且數值在 32 位有符號整數范圍內。
請嘗試在線性時間復雜度和空間復雜度的條件下解決此問題。

一個桶代表的是一個區間，根據數組元素的大小劃分到不同的桶里面，采用一個二維數組維護一個桶內的最大值和最小值，因為桶內的區間劃分的時候是最小間隔（反證法可得），所以不需要考慮桶內的差值，只需要計算桶間的最大差值。

代碼

class Solution {public int maximumGap(int[] nums) {int n = nums.length;if (n < 2) return 0;int max = Arrays.stream(nums).max().getAsInt();int min = Arrays.stream(nums).min().getAsInt();//劃分區間int gap = Math.max((max - min)/(n - 1),1);//找出最小的區間間隔int size = (max - min) / gap + 1;//桶的數量int[][] bucket = new int[size][2];for (int i = 0; i < size; i++) Arrays.fill(bucket[i], -1);//空桶設為-1for (int i = 0; i < n; i++) {int cur = (nums[i] - min) / gap;//當前元素所要放置的桶的序號if (bucket[cur][0] == -1) {//桶是空的，直接插入bucket[cur][0] = bucket[cur][1] = nums[i];} else {bucket[cur][0] = Math.min(nums[i], bucket[cur][0]);//更新桶內的最大最小值bucket[cur][1] = Math.max(nums[i], bucket[cur][1]);}}int res =0, pre = -1;for (int i = 0; i < size; i++)//遍歷所有桶，找出桶間最大間隔，空桶忽略不計{if(bucket[i][0]==-1) continue;if(pre!=-1) res= Math.max(res,bucket[i][0]-bucket[pre][1]);pre=i;}return res;}
}