Maximum Gap -- leetcode

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.

基本思路：

先求出無序數組中的最大值和最小值。

當每個數，都等距離分布時，此時将取得max gap的下限值。

span = ceiling[(B - A) / (N - 1)]

其中，B為最小值，A為最大值，N為元素個數

如果以此span作為一個桶的取值範圍。 并将數配置設定進這些桶内。

那麼在同一個桶内的數，之間的有序gap，将不會超過span。則桶内的數的，彼此之間就不用再求gap。

隻需要計算桶與桶之間的gap，并保留最大值。

而桶與桶之間的gap，則是後一桶的最小值，與 前一桶的最大值之間的內插補點。

故在配置設定時，隻需要記住該桶内的最小值，和最大值。

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2)
            return 0;
        int minV = nums[0];
        int maxV = nums[0];
        for (auto i: nums) {
            if (i < minV)
                minV = i;
            else if (i > maxV)
                maxV = i;
        }
        
        if (maxV == minV)
            return 0;
        
        int span = (maxV-minV) / (nums.size()-1);
        span = max(1, span);
        int buckets_count = (maxV-minV)/span;
        ++buckets_count;
        
        vector<int> buckets_min(buckets_count, INT_MAX);
        vector<int> buckets_max(buckets_count, INT_MIN);
        
        for (auto i: nums) {
            int slot = (i-minV) / span;
            buckets_min[slot] = min(buckets_min[slot], i);
            buckets_max[slot] = max(buckets_max[slot], i);
        }
        
        int gap = 0;
        int last_max = buckets_max[0];
        for (int i=1; i<buckets_count; i++) {
            if (buckets_max[i] != INT_MIN) {
                gap = max(gap, buckets_min[i]-last_max);
                last_max = buckets_max[i];
            }
        }
        return gap;
    }
};