題目：
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.

解答：
這題挺難理解的，但是可以舉例，比如說現(xiàn)在有1, 3, 5, 9。那么我們可以把它分成3個(gè)bucket來(lái)裝，min表示在這個(gè)bucket范圍中，存在的最小數(shù)和最大數(shù)。這個(gè)bucket的長(zhǎng)度是最小可能的最大差值。（如果哪個(gè)差值比這個(gè)還小，那么為了填補(bǔ)這個(gè)小差值，就必然存在另一個(gè)差值比它大，那么這個(gè)數(shù)組的最大差值就比當(dāng)前bucket大。所以均分下來(lái)的bucket是最小可能的最大差值）

b0: (1, 3) min = Integer.max, max = Integer.min
b1: (4, 6) min = Integer.max, max = Integer.min
b2: (7, 9) min = Integer.max, max = Integer.min

然后我們來(lái)看這個(gè)數(shù)組里的數(shù)在哪個(gè)bucket里，用(nums(i) - min) / gap來(lái)得到，
第一個(gè)數(shù)1在b0中，所以我們更新:
b0: (1, 3) min = 1, max = 1;
第二個(gè)數(shù)3在b0中，所以我們更新：
b0: (1, 3) min = 1, max = 3;
第三個(gè)數(shù)5在b1中，所以我們更新：
b1: (4, 6) min = 5, max = 5;
.
.
依次這樣下去。
因?yàn)槊總€(gè)bucket中的最大值－最小值就是我們最小的gap, 所以我們不用計(jì)算相鄰的兩個(gè)數(shù)，我們只要比較后一個(gè)bucket中的最小值和前一個(gè)bucket中的最大值相差多少，取最大相差的值就是最終的結(jié)果。注意考慮min和max兩個(gè)邊界值也要加進(jìn)去。

public int maximumGap(int[] nums) {if (nums == null || nums.length < 2) return 0;int len = nums.length;int max = nums[0], min = nums[0];for (int i = 0; i < nums.length; i++) {max = Math.max(max, nums[i]);min = Math.min(min, nums[i]);}//Math.ceil與最小的比這個(gè)數(shù)大的蒸熟，使bucket可以包含所有數(shù)int gap = (int)Math.ceil((double)(max - min) / (len - 1));int[] BucketsMIN = new int[len - 1];int[] BucketsMAX = new int[len - 1];Arrays.fill(BucketsMIN, Integer.MAX_VALUE);Arrays.fill(BucketsMAX, Integer.MIN_VALUE);for (int num : nums) {//不考慮邊界，所以把邊界的min和max都拿出來(lái)，單獨(dú)再考慮if (num == min || num == max) continue;int bucket = (num - min) / gap;BucketsMIN[bucket] = Math.min(BucketsMIN[bucket], num);BucketsMAX[bucket] = Math.max(BucketsMAX[bucket], num);}int result = 0;int previous = min;for (int i = 0; i < len - 1; i++) {if (BucketsMIN[i] == Integer.MAX_VALUE && BucketsMAX[i] == Integer.MIN_VALUE) {continue;}result = Math.max(result, BucketsMIN[i] - previous);previous = BucketsMAX[i];}result = Math.max(result, max - previous);return result;}

總結(jié)

以上是生活随笔為你收集整理的164. Maximum Gap的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。