LeetCode 164 Maximum Gap（桶排序）

Posted on | In | 阅读

这题既然是hard，那么就肯定要求复杂度在O(1)内完成。

考虑桶排序的方法，n个数大小相差最多为m的，那么大小相邻的两个数之间的间隔不会大于m / (n+1)

然后只要按照这个间隔构造足够的桶，维护每个桶中的最大值和最小值，同一个桶中的数字间隔不会多余答案所以只需要考虑每个桶的最小值与前面出现的最大值之间的差值就可以了。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int len = nums.size();
        if(len < 2){
            return 0;
        }
        int mi = INT_MAX, mx = INT_MIN;
        for(int i = 0; i < len; i++){
            mi = min(mi, nums[i]);
            mx = max(mx, nums[i]);
        }
        if(mi == mx)
            return 0;
        double bracket_size = (mx - mi) * 1.0 / (len - 1.0);
        int bracket_num = floor((mx - mi) / bracket_size + 1);
        vector<int> bracket_mx(bracket_num, INT_MIN);
        vector<int> bracket_mi(bracket_num, INT_MAX);
        for(int i = 0; i < len; i++){
            int pos = floor((nums[i] - mi) / bracket_size);
            bracket_mx[pos] = max(bracket_mx[pos], nums[i]);
            bracket_mi[pos] = min(bracket_mi[pos], nums[i]);
        }
        int ans = INT_MIN;
        int pre_max = bracket_mx[0];
        for(int i = 1; i < bracket_num; i++){
            if(bracket_mi[i] != INT_MAX){
                ans = max(ans, bracket_mi[i] - pre_max);
                pre_max = bracket_mx[i];
            }
        }
        return ans;
    }
};