题目链接：Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

这道题的要求是在无序数组中找到排序后元素减的最大间隔（数组元素非负）。

  1. sort

先排序，然后遍历一遍就可以找到最大间隔了。

时间复杂度：O(nlogn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution
{
public:
    int maximumGap(vector<int> &num)
    {
        if(num.size() < 2)
            return 0;
        
        sort(num.begin(), num.end());
        
        int maxg = 0;
        for(int i = 1; i < num.size(); ++ i)
            if(num[i] - num[i - 1] > maxg)
                maxg = num[i] - num[i - 1];
        
        return maxg;
    }
};

  1. bucket

上面的排序方案，不是线性的复杂度。要想达到O(n)的复杂度，可以考虑类似于桶排的思路。

假设n个元素的数值范围是[a, b]，那么最大间隙将不会小于(b-a)/(n-1)。因此令每个bucket宽度为len = ceil[(b-a)/(n-1)]（向上取整），因此最多会产生m = (b-a)/len+1个bucket。对于数组中的每个元素num[i]，可以计算出它应属于的bucket（loc = (num[i]-a)/len）。由于同一个bucket之间最大间隔最多是len-1，因此，最终的答案将不会在同一个bucket直接，所以只需要维护每个bucket中的最大值和最小值即可。因此，对于每一个非空的bucket（p），找到下一个非空的bucket（q），因此q.min - p.max就有可能是最大间隔。

————参考自《编程珠玑》。

时间复杂度：O(n)

空间复杂度：O(n)

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
35
36
37
38
39
40

class Solution
{
public:
    int maximumGap(vector<int> &num)
    {
        if(num.size() < 2)
            return 0;
        
        int n = num.size();
        // 数字范围[a, b]
        int a = *min_element(num.begin(), num.end());
        int b = *max_element(num.begin(), num.end());
        // 每个bucket宽度len，bucket数量m
        int len = ceil((b - a) / (n - 1.0)), m = (b - a) / len + 1;
        // bucket[i][0]存储最小值，bucket[i][1]存储最大值
        vector<vector<int>> bucket(m);
        
        for(int i = 0; i < n; ++ i)
        {
            int loc = (num[i] - a) / len;
            if(bucket[loc].size() == 0)
                bucket[loc] = {num[i], num[i]};
            else
            {
                bucket[loc][0] = min(bucket[loc][0], num[i]);
                bucket[loc][1] = max(bucket[loc][1], num[i]);
            }
        }
        
        // 寻找最大间隙
        int res = 0, pre = a;
        for(int i = 0; i < m; ++ i)
            if(bucket[i].size() != 0)
            {
                res = max(res, bucket[i][0] - pre);
                pre = bucket[i][1];
            }
        return res;
    }
};