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.

 代码一（简单易懂版）：

桶排序，由于num中的数字肯定在[min,max]区间内，所以根据抽屉原理，假设num中有n个数字，则最大的gap必然要大于dis=(max- min)/(n-1)，所以我们可以把num所在的范围分成等间隔的区间，相邻区间内的元素之间的最大差值，即为要寻找的gap。

 class Solution {
  public:
      int maximumGap(vector<int> &num) {
          int n = num.size();
          if (n < 2) return 0;
          if (n == 2) return abs(num[0] - num[1]);
          int imin = num[0], imax = num[0];
          for (int i = 0; i < n; ++i) {
              imin = min(imin, num[i]);
             imax = max(imax, num[i]);
         }
         int dist = (imax-imin) / n + 1;
         vector<vector<int> > bucket((imax-imin)/dist + 1);
         int idx;
         for (int i = 0; i < n; ++i) {
             idx = (num[i] - imin) / dist;
             if (bucket[idx].empty()) {
                 bucket[idx].push_back(num[i]);
                 bucket[idx].push_back(num[i]);
             } else {
                 bucket[idx][0] = min(bucket[idx][0], num[i]);
                 bucket[idx][1] = max(bucket[idx][1], num[i]);
             }
         }
         int gap = 0, pre = 0, tmp;
         for (int i = 1; i < bucket.size(); ++i) {
             if (bucket[i].empty()) continue;
             tmp = bucket[i][0] - bucket[pre][1];
             gap = max(gap, tmp);
             pre = i;
         }
         return gap;
     }
 };

代码二（刚开始我看的一直是这个，代码风格虽然很好，但是不好理解）：

这里要用到桶排序，感觉不太感兴趣，就直接看了网上的做法。

（ps:后来才知道，桶排序是基数排序的基础）

C++中vector中的一些常用函数：

取容器中的最大最小值min_element(),max_element()。

当有必要对一个接受pair参数的函数传递两个值时， make_pair()尤其显得方便。

int minAll = *min_element(nums.begin(), nums.end());

int maxAll = *max_element(nums.begin(), nums.end());

vector<pair<int, int> > buckets(bucketCount, make_pair(INT_MIN, INT_MAX));

应用桶排序的思想，把数组元素归到桶中。在一个桶内，元素差小于等于block.max-block.min。在两桶之间，元素差等于block2.min-block1.max。 
// 用桶排序
 // 算出相邻两个桶之间的最大差值
 // 如果是平均分布，则桶的数目和元素的数目相同时，其排序的时间复杂度是0(n)
 // 我们假设桶的个数和元素的数目相同，若是平均分布，则每个桶里有一个数，而若某个桶里有两个以上的桶时，这时必有至少一个是空桶，那么最大间隔可能就落在空桶的相邻两个桶存储的数之间，最大间隔不会落在同一个桶的数里，因此我们不需要对每个桶再排一次序，只需要记录同一个桶的最大值和最小值，算出前一个有最大值的桶和后一个有最小值的桶之差，则可能是最大间隔
 //步骤：1.算好用的桶的个数，用最大元素和最小元素算出平均间隔，记录在平均间隔上的最大值和最小值，
 // 2. 再算出前一个间隔里的最大值和后一个间隔里的最小值之差，取最大的一个，
 // 3. 再算出最小值和第二小的差（平均间隔最小值第一个），最大值和第二大（平均间隔最大值最后一个）的差，三个值相比，取最大的，就是最大间隔

class Solution {
public:
    int maximumGap(vector<int>& nums) {
         if (num.size() < 2) return 0;
        // 1. 算出用的桶数：取平均间隔，再用最大值和最小值之差除以间隔，得到桶数
        // 因为假设所有值都是平均分布的时候，如此取桶数可得时间复杂度是0(n)
        auto maxVal = *max_element(num.begin(), num.end());
        auto minVal = *min_element(num.begin(), num.end());
        int agGap = ceil((double)(maxVal - minVal) / (num.size()-1)); // 平均间隔
        int bucketCount = ceil((double)(maxVal - minVal) / agGap);
        // 2. 记录每个桶的最大值和最小值
        vector<pair<int, int> > buckets(bucketCount, make_pair(INT_MIN, INT_MAX)); // 初始化桶
        for (auto val : num){
            if (val == maxVal || val == minVal) continue;
            int bucketNum = (val - minVal) / agGap;
            if (val > buckets[bucketNum].first) 
                buckets[bucketNum].first = val; // 存储最大值
            if (val < buckets[bucketNum].second) buckets[bucketNum].second = val; // 存储最小值
        }
        // 3. 算出最大间隔
        int maxGap(0), lastMax(minVal);
        for (auto bucket : buckets){
            if (bucket.first == INT_MIN) continue; // 空桶
            int curMax(bucket.first), curMin(bucket.second);
            maxGap = max(maxGap, curMin - lastMax);
            lastMax = curMax;
        }
        maxGap = max(maxGap, maxVal - lastMax);
        return maxGap;
        
    }
};