数组中的最大间距（巨难）

1.对应letecode链接：

164. 最大间距 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

1.我们很容易就能够想到时间复杂度为O（N*logN)的算法，然后再遍历一遍数组求相邻两个数的最大差值即可。但这与题目要求的时间复杂度O（N）不符。

下面我们来看一下这种不是人能够想得到的解法：

2.利用计数排序的思想，先求出原数组的最大值 max 与最小值 min .

利用桶排序的思想，根据原数组的长度 n，创建出 n 个桶，每一个桶代表一个区间范围。其中第 0个桶从原数组的最小值 min 开始，区间跨度为(max - min) / (n - 1)。下面我们以无序数组 { 2, 6, 3, 4, 5, 10, 9 }为例：

3.遍历所有的桶，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值

第 2 步，遍历原数组，确定每个桶内的最大和最小值。

3.遍历原数组，把原数组每一个元素插入到对应的桶中，记录每一个桶的最大和最小值。

4.对应代码：

 

class Solution {
public:
    int maximumGap(vector& nums) {
          if(nums.size()<2){
              return 0;
          }
          int len=nums.size();
          int MaxVal=INT_MIN;
          int MinVal=INT_MAX;
          for(auto ch:nums)
          {
              MaxVal=max(MaxVal,ch);
              MinVal=min(MinVal,ch);
          }
          if(MinVal==MaxVal){//说明只有一种数
              return 0;
          }
          //不止一种数一定有range,len个数len+1一个桶
          vectorhasNum(len+1);
          //保存第i号桶的最大值和最小值
          vectormaxs(len+1);
          vectormins(len+1);
          int bid=0;
          for(int i=0;i 

注意：代码实现这里N个数对应N+1个桶原理类似。