博文中会简要介绍Leetcode P0164题目分析及解题思路。
“Maximum Gap”是一道很有意思的题目，这道题考察的核心是排序算法，题目中要求解题者尝试在线性时间内得到结果，而我们所知道的基于比较的排序基本都是O(nlogn)的时间复杂度，所以这道题考察的其他更加精妙的排序算法，例如基数排序和桶排序。
这篇博文参考了Leetcode上的活跃博主windliang的博文，会较为详细地阐述基数排序和桶排序的原理。
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Note:
- You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
- Try to solve it in linear time/space.
朴素解法
最简单的想法是直接排序，然后扫一遍数组求出相邻数字的最大差即可。这个算法是O(nlogn)的。
以下是Java的题解代码实现。
class Solution {
public int maximumGap(int[] nums) {
int N = nums.length;
if (N < 2)
return 0;
Arrays.sort(nums);
int max = 0;
for (int idx=0; idx<N-1; ++idx) {
max = Math.max(nums[idx+1]-nums[idx], max);
}
return max;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int maximumGap(vector<int>& nums) {
int N = nums.size();
if (N < 2)
return 0;
sort(nums.begin(), nums.end());
int max_gap = 0;
for (int idx=0; idx<N-1; ++idx) {
max_gap = max(max_gap, nums[idx+1]-nums[idx]);
}
return max_gap;
}
};
基数排序
基数排序的时间复杂度是O(kn)，k是最大数字的位数，当k远小于n的时候，时间复杂度可以近似看成O(n)。下面讲一下具体思想。
比如这样一个数列排序：342 58 576 356，我们运用基数排序算法对其进行排序，
不足的位数看做是 0
342 058 576 356
按照个位将数字依次放到不同的位置
0:
1:
2: 342
3:
4:
5:
6: 576, 356
7:
8: 058
9:
把上边的数字依次拿出来，组成新的序列 342 576 356 058，然后按十位继续放到不同的位置。
0:
1:
2:
3:
4: 342
5: 356 058
6:
7: 576
8:
9:
把上边的数字依次拿出来，组成新的序列 342 356 058 576，然后按百位继续装到不同的位置。
0: 058
1:
2:
3: 342 356
4:
5: 576
6:
7:
8:
9:
把数字依次拿出来，最终结果就是58 342 356 576
为了代码更好理解， 我们可以直接用10个list去存放每一组的数字，官方题解是直接用一维数组实现的。对于取各个位的的数字，我们通过对数字除以10的整数倍，然后再对10取余来实现。
以下是Java的题解代码实现。
public int maximumGap(int[] nums) {
if (nums.length <= 1) {
return 0;
}
List<ArrayList<Integer>> lists = new ArrayList<>();
for (int i = 0; i < 10; i++) {
lists.add(new ArrayList<>());
}
int n = nums.length;
int max = nums[0];
//找出最大的数字
for (int i = 1; i < n; i++) {
if (max < nums[i]) {
max = nums[i];
}
}
int m = max;
int exp = 1;
//一位一位的进行
while (max > 0) {
//将之前的元素清空
for (int i = 0; i < 10; i++) {
lists.set(i, new ArrayList<>());
}
//将数字放入对应的位置
for (int i = 0; i < n; i++) {
lists.get(nums[i] / exp % 10).add(nums[i]);
}
//将数字依次拿出来
int index = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < lists.get(i).size(); j++) {
nums[index] = lists.get(i).get(j);
index++;
}
}
max /= 10;
exp *= 10;
}
int maxGap = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] - nums[i] > maxGap) {
maxGap = nums[i + 1] - nums[i];
}
}
return maxGap;
}
桶排序
简介
我们知道如果是有序数组的话，我们就可以通过计算两两数字之间差即可解决问题。
那么如果是更宏观上的有序呢？这就用到了桶排序的想法，桶排序是一种非基于比较的排序方法。
一般来说基于比较的排序方法的平均时间复杂度的最优下界是O(nlogn)，而桶排序不是基于比较来实现排序的，它借鉴了哈希算法的思想，如果一个数，比它小的数哈希值比它小，比它大的数哈希值比它大，那么我们可以直接使用这个哈希函数f(·)，通过映射来得到一个有序数组。
不过桶排序的缺点其实也很明显。极限情况下我们希望每个桶里面只有一个数，但是这很难满足。最大的原因是如果一组数据的上下界差值过大，但数据本身数量并不大，我们也需要非常大的空间来存储，因为桶的个数取决与上下界差和数据量。在这种情况下，会造成极大的空间浪费。
而如果桶内数据过多，那么桶排序的优势会退化。由于我们在桶内是使用朴素的排序方法，例如插入排序、快排序和归并排序，所以如果桶内数据过多，桶排序也会退化为O(nlogn)的时间复杂度。
虽然我们也可以使用rehash原理，对桶内数据继续采取桶排序，但是总而言之，桶排序确实具有一定的局限。在数据上下界确定，重复量少，插入删除比较少的情况下（即主要以查询为主），桶排序有很大的优势，反之自身的优势则会退化。
题解
这道题非常适合使用桶排序，下面讲解使用桶排序的解法，
我们把 0 3 4 6 23 28 29 33 38 依次装到三个箱子中
0 1 2 3
------- ------- ------- -------
| 3 4 | | | | 29 | | 33 |
| 6 | | | | 23 | | |
| 0 | | | | 28 | | 38 |
------- ------- ------- -------
0 - 9 10 - 19 20 - 29 30 - 39
我们把每个箱子的最大值和最小值表示出来
min max min max min max min max
0 6 - - 23 29 33 38
我们可以只计算相邻箱子min和max的差值来解决问题吗？空箱子直接跳过，比如说，
第2个箱子的min减第0个箱子的max，23-6=17
第3个箱子的min减第2个箱子的max，33-29=4
看起来没什么问题，但这样做一定需要一个前提，因为我们只计算了相邻箱子的差值，没有计算箱子内数字的情况，所以我们需要保证每个箱子里边的数字一定不会产生最大gap。
我们把箱子能放的的数字个数记为interval，给定的数字中最小的是min，最大的是max。那么箱子划分的范围就是[min, min+1*interval-1)，[min+1*interval, min+2*interval-1)，……，[min+k*interval, max+1)，上边举的例子中，我们取了10作为interval。
划定了箱子范围后，我们其实很容易把数字放到箱子中，通过(nums[i]-min)/interval即可得到当前数字应该放到的箱子编号。那么最主要的问题其实就是怎么去确定interval。
-
interval过小的话，需要更多的箱子去存储，很费空间，此外箱子增多了，比较的次数也会增多，不划算。 -
interval过大的话，箱子内部的数字可能产生题目要求的最大gap，所以肯定不行。
所以我们要找到那个保证箱子内部的数字不会产生最大gap，并且尽量大的interval。
像上边的例子，如果我们保证至少有一个空箱子，那么我们就可以断言，箱子内部一定不会产生最大gap。因为在我们的某次计算中，会跳过一个空箱子，那么得到的gap一定会大于interval，而箱子中的数字最大的gap是interval-1。
接下来的问题，怎么保证至少有一个空箱子呢？
鸽巢原理的变形，有n-2个数字，如果箱子数多于n-2，那么一定会出现空箱子。总范围是max-min，那么interval=(max-min)/M，为了使得interval尽量大，箱子数M取最小即可，也就是n-1。
所以interval=(max-min)/n-1。这里如果除不尽的话，我们interval可以向上取整。因为我们给定的数字都是整数，这里向上取整的话对于最大gap是没有影响的。比如原来范围是[0,5.5)，那么内部产生的最大gap是5-0=5。现在向上取整，范围变成[0,6)，但是内部产生的最大gap依旧是5-0=5。
以下是Java的题解代码实现。
public int maximumGap(int[] nums) {
if (nums.length <= 1) {
return 0;
}
int n = nums.length;
int min = nums[0];
int max = nums[0];
//找出最大值、最小值
for (int i = 1; i < n; i++) {
min = Math.min(nums[i], min);
max = Math.max(nums[i], max);
}
if(max - min == 0) {
return 0;
}
//算出每个箱子的范围
int interval = (int) Math.ceil((double)(max - min) / (n - 1));
//每个箱子里数字的最小值和最大值
int[] bucketMin = new int[n - 1];
int[] bucketMax = new int[n - 1];
//最小值初始为 Integer.MAX_VALUE
Arrays.fill(bucketMin, Integer.MAX_VALUE);
//最小值初始化为 -1，因为题目告诉我们所有数字是非负数
Arrays.fill(bucketMax, -1);
//考虑每个数字
for (int i = 0; i < nums.length; i++) {
//当前数字所在箱子编号
int index = (nums[i] - min) / interval;
//最大数和最小数不需要考虑
if(nums[i] == min || nums[i] == max) {
continue;
}
//更新当前数字所在箱子的最小值和最大值
bucketMin[index] = Math.min(nums[i], bucketMin[index]);
bucketMax[index] = Math.max(nums[i], bucketMax[index]);
}
int maxGap = 0;
//min 看做第 -1 个箱子的最大值
int previousMax = min;
//从第 0 个箱子开始计算
for (int i = 0; i < n - 1; i++) {
//最大值是 -1 说明箱子中没有数字，直接跳过
if (bucketMax[i] == -1) {
continue;
}
//当前箱子的最小值减去前一个箱子的最大值
maxGap = Math.max(bucketMin[i] - previousMax, maxGap);
previousMax = bucketMax[i];
}
//最大值可能处于边界，不在箱子中，需要单独考虑
maxGap = Math.max(max - previousMax, maxGap);
return maxGap;
}