## Maximum Gap

### 描述

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.

### 分析

### 解法1 桶排序

{% if book.java %}
```java
// Maximum Gap
// Bucket Sort
// Time Complexity: O(n+k), Space Complexity: O(n+k)
public class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2) return 0;
bucketSort(nums);

int maxDiff = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; ++i) {
maxDiff = Math.max(maxDiff, nums[i] - nums[i - 1]);
}
return maxDiff;
}

private static void bucketSort(int[] nums) {
if (nums.length < 2) return;
int minValue = Integer.MAX_VALUE;
int maxValue = Integer.MIN_VALUE;

for (int i : nums) {
minValue = Math.min(minValue, i);
maxValue = Math.max(maxValue, i);
}

final int bucketSize = (maxValue - minValue) / nums.length + 1;
final int bucketCount = (maxValue - minValue) / bucketSize + 1;
final ArrayList[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < buckets.length; ++i) {
buckets[i] = new ArrayList<>();
}

for (int x : nums) {
final int index = (x - minValue) / bucketSize;
}

for (final ArrayList list : buckets) {
Collections.sort(list);
}

int i = 0;
for (final ArrayList list : buckets) {
for (int x : list) {
nums[i++] = x;
}
}
}
}
```
{% endif %}

### 解法2 基数排序

{% if book.java %}
```java
// Maximum Gap
// Time Complexity: O(nd), Space Complexity: O(n+d)
public class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2) return 0;

int maxDiff = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; ++i) {
maxDiff = Math.max(maxDiff, nums[i] - nums[i - 1]);
}
return maxDiff;
}
private static void radixSort(int[] nums) {
int minValue = Integer.MAX_VALUE;
int maxValue = Integer.MIN_VALUE;

for (int i : nums) {
minValue = Math.min(minValue, i);
maxValue = Math.max(maxValue, i);
}

final int D = Integer.toString(maxValue - minValue).length();
final ArrayList[] buckets = new ArrayList[10];
for (int i = 0; i < buckets.length; ++i) {
buckets[i] = new ArrayList<>();
}

for (int i = 0; i < D; ++i) {
for (int x : nums) {
final int index = getDigit(x - minValue, i);
final ArrayList bucket = buckets[index];
}

int index = 0;
for (ArrayList bucket : buckets) {
for (int x : bucket) {
nums[index++] = x;
}
bucket.clear();
}
}
}

// get the i-th digit of n
private static int getDigit(int n, int i) {
for (int j = 0; j < i; ++j) {
n /= 10;
}
return n % 10;
}
}
```
{% endif %}

### 解法3 计数排序

{% if book.java %}
{% codesnippet "./code/maximum-gap-3."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}