點擊上方"java全棧技術"關注，每天學習一個java知識點
小灰一邊回憶一邊講述起當時面試的情景......
題目：有一個無序整型數組，如何求出這個數組排序後的任意兩個相鄰元素的最大差值？要求時間和空間複雜度儘可能低。（例如：無序數組 2,3,1,4,6，排序後是1,2,3,4,6，最大差值是6-4=2）
解法一：
用一種較快的穩定排序算法（比如歸併算法，時間複雜度N*logN）給原數組排序，然後遍歷排好序的數組，每兩個相鄰元素求差，最終得到最大差值。
該解法的時間複雜度是O（N*logN），在不改變原數組的情況下，空間複雜度是O（N）。
解法二：
1.利用計數排序的思想，先求出原數組的最大值Max與最小值Min的區間長度k（k=Max-Min+1）。
2.創建一個長度為k的新數組Array。
3.遍歷原數組，把原數組每一個元素插入到新數組Array對應的位置，比如元素的值為n，則插入到Array[n-min]當中。此時Array的部分位置為空，部分位置填充了數值。
4.遍歷新數組Array，統計出Array中最大連續出現空值的次數+1，即為相鄰元素最大差值。
例如給定無序數組 { 2, 6, 3, 4, 5, 10, 9 }，處理過程如下圖：
該解法的時間複雜度為O（n+k），空間複雜度同樣是O（n+k）。
解法三：
1.利用桶排序的思想，先求出原數組從最小值Min到最大值Max的單位區間長度d，d=(Max-Min)/n。算出d的作用是為了後續確定各個桶的區間範圍劃分。
2.創建一個長度是N+1的數組Array，數組的每一個元素都是一個List，代表一個桶。
3.遍歷原數組，把原數組每一個元素插入到新數組Array對應的桶當中，進入各個桶的條件是根據不同的數值區間（數值區間如何劃分，看後面的圖就明白了）。由於桶的總數量是N+1，所以至少有一個桶是空的。
4.遍歷新數組Array，計算每一個空桶右端非空桶中的最小值，與空桶左端非空桶的最大值的差，數值最大的差即為原數組排序後的相鄰最大差值。
例如給定無序數組 { 0, 6, 3, 16, 7, 10, 9, 11, 20, 18 }，處理過程如下圖：
該解法的時間複雜度為O（n），空間複雜度同樣是O（n）。
十分鐘後......
以上就是小灰面試的情況......
閱讀更多 java全棧技術 的文章
