164. Maximum Gap

https://leetcode.com/problems/maximum-gap/

对给定数组找元素值之间最大的gap。gap问题十有八九都和bucket sort有关。按照range == [max - min]分成N个bucket, 这样能保证至少存在一个gap大于等于bucket size。然后根据元素值分配bucket。最后遍历每个bucket，它的min减去上个bucket的max最优解即全局最优解。因为分成bucket后max gap候选只能是bucket内或跨bucket（即b_min-上个b_max）。分下来如果有bucket分到了多余一个元素，说明有的bucket为空，空bucket两边元素距离大于bucket size，bucket内gap不能是max gap；如果每个bucket刚好分到一个，不存在bucket内gap，所以遍历得到max(b_min - 上个b_max)即解。

/*
 * @lc app=leetcode id=164 lang=cpp
 *
 * [164] Maximum Gap
 */
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        const int N = nums.size();
        if (N == 0) return 0;
        int mx = INT_MIN, mi = INT_MAX, res = 0;
        for (const int num : nums) {
            mx = max(mx, num);
            mi = min(mi, num);
        }
        const int b_size = (mx - mi) / N + 1;
        vector<int> mins(N, INT_MAX), maxs(N, INT_MIN);
        for (const int num : nums) {
            const int ind = (num - mi) / b_size;
            mins[ind] = min(mins[ind], num);
            maxs[ind] = max(maxs[ind], num);
        }
        for (int i = 1, pre = 0; i < N; ++i) {
            if (mins[i] == INT_MAX) continue;
            res = max(res, mins[i] - maxs[pre]);
            pre = i;
        }
        return res;
    }
};