1. 題目要求

給定無序數組(此數組是long類型的數組，但以下示例只列一些小一點的數)，例如：

[3, 1, 12, 9, 3, 7, 1, 4, 7, 8, 10]

求數組有序后相鄰元素之間的最大差值，數組有序后如下：

[1, 1, 3, 3, 4, 7, 7, 8, 9, 10, 12]

可以發現數組有序后相鄰元素之間的最大差值為3：

要求寫一個算法實現此題目，且時間復雜度為O(n)

2. 題目分析

題目要求是求數組有序后相鄰元素之間的最大差值，那么需要對數組進行排序嗎？

8大經典排序排序算法中，時間復雜度最低的為桶排序，其時間復雜度為O(n)，但是由于數組是long類型的，其中的數可能很大，例如假設數組中只有3個數，100128124、12912312和8231，假如使用桶排序的話需要準備一個長度為100128124的額外數組用于排序(參考桶排序)，這樣顯然太坑了吧。

于是我們考慮使用"桶排序"的思想來做這個題目，但是不對數組進行排序。

3. 實現思路

(1) 假設無序數組的長度為9，其中元素的取值范圍為[0, 49]，即數組的最小值為0，最大值為49

(2) 準備10(數組長度+1)個"桶"，平分數組取值范圍，即10個"桶"，假設編號為0~9，那么0號桶裝的數字為[0, 4]，1號桶裝的數字為[4, 9]，以此類推，9號桶裝的數字的范圍為[45, 49]

(3) 遍歷數組，將每個元素裝入對應的"桶"中

到這里后，我們可以得出以下重要的結論：

結論一：因為我們準備了 N+1 個桶，數組的長度為N，所以必然有>=1個桶是空桶，另外可以確定的是，最小值一定放在第一個桶中，最大值一定放在最后一個桶中，所以第一個桶和最后一個桶一定不是空桶。

結論二：一個空桶的左邊的第一個非空桶中的最大值和它右邊第一個非空桶中的最小值，在數組有序后一定是相鄰的，例如2號桶是空桶，它左邊的第一個非空桶是0號桶，0號桶的最大值為3,2號桶右邊的第一個非空桶是3號桶，3號桶的最小值為17，在數組有序后，3和17一定是相鄰的。

結論三：一個空桶的左邊第一個非空桶中的最大值與它右邊第一個非空桶中的最小值的差值一定大于這個空桶的取值范圍的差值。于是我們發現，要求數組有序相鄰元素之間的最大差值，不需要考慮桶內部的差值，桶內部的差值最大為4(示例中桶內部的最大差值)，而由于有空桶的存在，所以數組有序后相鄰元素之間的最大差值肯定是大于4的。于是我們發現，只要記錄每個桶的最大值和最小值就可以得到最終的結果。

(4) 遍歷所有的非空桶，記錄前一個桶的最大值和后一個桶的最小值的差值，這些差值中的最大值就是我們題目的最終結果。

4. Java代碼實現

本文同步分享在 博客“CoderJed”(JianShu)。

如有侵權，請聯系 support@oschina.cn 刪除。

本文參與“OSC源創計劃”，歡迎正在閱讀的你也加入，一起分享。

總結

以上是生活随笔為你收集整理的java 数组中差值最大数对,[算法题] 求数组有序后相邻元素之间的最大差值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。