Joyce' Blog
0%

maximum-gap

发表于 更新于

题目描述

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

说明:

  • 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
  • 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

题解

太难了嘤，看了题解都还是不会写。总的来说就是用了桶排序和鸽笼原理吧。用桶将元素分类，不用比较每两个元素，而只需要比较这些桶即可。

  • 鸽笼原理：n 个物品放入 m 个容器中，如果 n > m 那么一定有一个容器装有至少两个物品。

若有 n 个元素，最大值为 max，最小值为 min，那么间距 t 最小为：( max - min ) / ( n - 1 )。

最关键的在于桶的大小。桶的大小是可以容纳的最大区间的范围，桶内实际区间范围大小等于桶内最大值减最小值，桶的大小 b 应该小于最小间距 t 且不小于 1 。比较相邻桶的时候，只需要比较前一个痛的最大值和后一个桶的最小值。桶的个数 k 为$⌈(max−min)/b⌉$。第 i 个桶保存的值区间为： $[min+i∗b, min+(i+1)∗b)$，由$\lfloor (num - min)/b$ 可以算出 num 属于哪个桶。

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
class Bucket{
public:
    bool used=false;
    int min=INT_MAX;
    int max=INT_MIN;
};
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int size=nums.size();
        if(size<2)return 0;
        int maxElem=*max_element(nums.begin(),nums.end());
        int minElem=*min_element(nums.begin(),nums.end());
        int bucketSize=max(1,(maxElem-minElem)/(size-1));
        int bucketNum=(maxElem-minElem)/bucketSize+1;
        vector<Bucket> buckets(bucketNum);
        for(int i=0;i<size;i++)
        {
            int k=nums[i];
            int index=(k-minElem)/bucketSize;
            buckets[index].used=true;
            buckets[index].min=min(k,buckets[index].min);
            buckets[index].max=max(k,buckets[index].max);
        }
        int maxGap=buckets[0].max-buckets[0].min;
        int lastMax=buckets[0].max;
        for(int i=1;i<bucketNum;i++)
        {
            if(buckets[i].used)
            {
                maxGap=max(buckets[i].min-lastMax,maxGap);
                lastMax=buckets[i].max;
            }
        }
        return maxGap;
    }
};

执行用时：16 ms, 在所有 C++ 提交中击败了54.55%的用户

内存消耗：8.9 MB, 在所有 C++ 提交中击败了54.67%的用户

时间复杂度：$O(n + b) \approx O(n))$。

线性遍历一遍数组中的元素，复杂度为 $O(n)$。找到桶之间的最大间距需要线性遍历一遍所有的桶，复杂度为$O(b)$。所以总复杂度是线性的。

空间复杂度：$O(2 \cdot b) \approx O(n)$的额外空间。

每个桶只需要存储最大和最小元素，因此额外空间和桶个数线性相关。

链接：https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<limits.h>//INT_MAX与INT_MIN的头文件
using namespace std;
void minNote()
{
	int imax = 0x7fffffff;
	int imin = 0x80000000;
	cout << imax << endl << imin << endl << INT_MAX << endl << INT_MIN << endl;
	int maxLimit = numeric_limits<int>::max();
	int minLimit = numeric_limits<int>::min();
	cout << maxLimit << endl << minLimit << endl;
	cout << 0x7fffffff << endl << 0x80000000 << endl;
}

//输出：
2147483647
-2147483648
2147483647
-2147483648
2147483647
-2147483648
2147483647
2147483648
1
2
#include<algorithm>// std::min_element, std::max_element
max_element()与min_element()返回区间 [first,last)中第一个最大值和第一个最小值对应的迭代器。
1
vector(size_type Count);	创建一个大小为Count的向量vect