164. 最大间距

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

思路

1. 假设n个元素都落在集合[1, u]内，那么它们之间的最大间隙gap不会小于（u-l）/(n-1)。由于其值可能等于0，在此道题里没有意义，所以需要确保间隙必须大于等于1。
2. 于是，桶的个数定为（u-l）/gap+1。对于每个元素num，将会落在k=(num-l)/gap桶里。
3. 桶最大间隙就存在于桶间。

class Solution {
 public:
  int maximumGap(vector<int>& nums) {
    int size = nums.size();
    if (size < 2) return 0;

    int mini = *min_element(nums.begin(), nums.end());
    int maxi = *max_element(nums.begin(), nums.end());

    //为确保桶间空隙大于1
    int gapBetweenBuckets = max(1, (maxi - mini) / (size - 1));
    int numberOfBuckets = (maxi - mini) / gapBetweenBuckets + 1;

    //存储着每个桶里的最小值和最大值
    vector<int> bucketsMin(numberOfBuckets, INT_MAX);
    vector<int> bucketsMax(numberOfBuckets, INT_MIN);

    //遍历数组，确定每个桶里的最小值和最大值
    for (int num : nums) {
      //判断此数应该落在哪个桶里
      int k = (num - mini) / gapBetweenBuckets;
      if (num < bucketsMin[k]) bucketsMin[k] = num;
      if (num > bucketsMax[k]) bucketsMax[k] = num;
    }

    int i = 0, j;
    gapBetweenBuckets = bucketsMax[0] - bucketsMin[0];
    while (i < numberOfBuckets) {
      //算出此桶和下一个桶的间隙值
      j = i + 1;
      //跳过空桶
      while (j < numberOfBuckets && bucketsMax[j] == INT_MIN &&
             bucketsMin[j] == INT_MAX) {
        j++;
      }
      //此桶为最后一个桶了，没有下一个桶可以供其进行比较
      if (j == numberOfBuckets) break;
      gapBetweenBuckets = max(gapBetweenBuckets, bucketsMin[j] - bucketsMax[i]);
      i = j;
    }
    return gapBetweenBuckets;
  }
};