Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 164. Maximum Gap

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4234970.html

題目：


解答：

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

        int mn = *min_element(nums.begin(), nums.end());
        int mx = *max_element(nums.begin(), nums.end());

        int bk_size = max(1, (mx - mn) / (n - 1));
        int bk_count = ((mx - mn) / bk_size) + 1;

        vector<int> bk_min(bk_count, INT_MAX);
        vector<int> bk_max(bk_count, INT_MIN);
        vector<bool> used(bk_count, false);

        for (int num : nums) {
            int idx = (num - mn) / bk_size;
            bk_min[idx] = min(bk_min[idx], num);
            bk_max[idx] = max(bk_max[idx], num);
            used[idx] = true;
        }

        int pre = mn;
        int ans = 0;
        for (int i = 0; i < bk_count; ++i) {
            if (!used[i]) {
                continue;
            }

            ans = max(ans, bk_min[i] - pre);
            pre = bk_max[i];
        }

        return ans;
    }
};