Leetcode 164 Solution

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

        int min_val = INT_MAX;
        int max_val = INT_MIN;

        for (auto num : nums)
        {
            min_val = min(min_val, num);
            max_val = max(max_val, num);
        }

        int bucket_size = max((int)((max_val - min_val) / (nums.size() - 1)), 1);
        int bucket_num = (max_val - min_val) / bucket_size + 1;

        vector<int> min_buckets(bucket_num, INT_MAX);
        vector<int> max_buckets(bucket_num, INT_MIN);
        vector<bool> empty_buckets(bucket_num, true);

        for (auto num : nums)
        {
            int i = (num - min_val) / bucket_size;

            min_buckets[i] = min(min_buckets[i], num);
            max_buckets[i] = max(max_buckets[i], num);
            empty_buckets[i] = false;
        }

        int max_dist = 0;
        int pre = 0;
        for (int i = 1; i < nums.size(); i++)
        {
            if (empty_buckets[i])
                continue;

            max_dist = max(max_dist, min_buckets[i] - max_buckets[pre]);
            pre = i;
        }

        return max_dist;
    }
};