class Solution {public:    /**     * @param nums: a vector of integers     * @return: the maximum difference     */    int maximumGap(vector
     
       nums) {        // write your code here        int N = nums.size();        if (N < 2) return 0;        int m1 = *min_element(nums.begin(),nums.end());        int m2 = *max_element(nums.begin(),nums.end());        if (m1 == m2) return 0;                int M = static_cast
      
       (sqrt(N)) + 1;        vector
       
         interMin = vector
        
         (M,INT_MAX);        vector
         
           interMax = vector
          
           (M,INT_MIN); int W = (m2 - m1)/M + 1; auto a = vector
           
            
             >(M,vector
             
              {}); for (auto x : nums) { auto index = (x - m1)/W; a[index].push_back(x); interMin[index] = min(interMin[index],x); interMax[index] = max(interMax[index],x); } int ret = 0; for (auto x : a) ret = max(ret,maximumGap(x)); int last = INT_MIN; for (int i = 0;i
             
            
           
          
         
        
       
      
     

自己想了个蠢蠢的递归，是不是O(N)有待商榷

后来看了leetcode上的解答（顺便吐槽一下，这两个题库名字这么像），才知道

N个数有（N-1)个GAP，这些gap一共长m2-m1

平均长度是(double)(m2-m1)/(N-1), 因为CAP大小是整数, 所以最大的GAP比这个平均数大

所以最大GAP的最小值是W=（m2-m1-1)/(N-1) + 1 （注意排除m1=m2的情况）

这个思想是在YYJ老师的组合数学的课上学到的，很好用

另外这里有个小技巧，就是这个gap的表达式把（N-1)是不是整除(m2-m1) 的情况都包含了

这样我保证一个区间里面有W个元素，这个区间里面的最大GAP也是W-1

把x分到第(x-m1)/W个区间，m1分到第0个，m2分到第(m2-m1)/W个区间

//那么m2会不会分到m1的区间呢？不会，因为这样最大的GAP<=W-1与最大GAP最小是W矛盾。

一共有M= (m2-m1)/W+1个区间

这样我只要记录每个区间的最小值和最大值就行了

后来在leetcode上又码了一遍这个算法

class Solution {public:    int maximumGap(vector
     
      & nums) {        int N = nums.size();        if (N < 2) return 0;        int m1 = *min_element(nums.begin(),nums.end());        int m2 = *max_element(nums.begin(),nums.end());        if (m1 == m2) return 0;        int W = (m2 - m1 - 1)/(N - 1) + 1; //W = minGap                int M = (m2 - m1)/W + 1;        auto v = vector
      
       (M,false);        vector
       
         interMin = vector
        
         (M,INT_MAX);        vector
         
           interMax = vector
          
           (M,INT_MIN); for (auto x : nums) { auto index = (x - m1)/W; v[index] = true; interMin[index] = min(interMin[index],x); interMax[index] = max(interMax[index],x); } int ret = 0; int last = INT_MIN; for (int i = 0;i < M;i++) { if (!v[i]) continue; if (last >= 0) ret = max(ret,interMin[i] - last); last = interMax[i]; } return ret; }};