Concise C++ solution use buckets


  • 2
    A
    class Solution {
    public:
        int maximumGap(vector<int>& nums) {
            if (nums.size() < 2) {
                return 0;
            }
            int max_num = *max_element(nums.begin(), nums.end());
            int min_num = *min_element(nums.begin(), nums.end());
            if (max_num == min_num) {
                return 0;
            }
            float bucket_size = (float)(max_num - min_num) / nums.size();
            vector<pair<int, int>> buckets(nums.size() + 1, make_pair(INT_MAX, INT_MIN));
            for (auto i : nums) {
                int index = (int)((i - min_num) / bucket_size);
                buckets[index].first = min(buckets[index].first, i);
                buckets[index].second = max(buckets[index].second, i);
            }
            int max_gap = buckets[0].second - buckets[0].first;
            for (int i = 1, pre = buckets[0].second; i < buckets.size(); ++i) {
                if (buckets[i].first == INT_MAX) continue;
                max_gap = max(max_gap, max(buckets[i].second - buckets[i].first, buckets[i].first - pre));
                pre = buckets[i].second;
            }
            return max_gap;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.