At Beginning, I using the std::sort to make the vector in order, and then get the max gap, after submit it, it cost 52ms. Then I follow the solution provided by leetcode, and it cost 44ms, but it cost me almost 2 hours to finish it. It seems that sometimes I cost large time to get a solution which seems to be a good solution, and it may not reduce too much cost when comparing with some easy way.

```
#include <iostream>
#include <functional>
// Solution 1 cost 52ms
int solution_1(std::vector<int> &num)
{
if (num.size() < 2)
{
return 0;
}
std::sort(num.begin(), num.end());
int gap = 0;
for(int n = 0, m = 1; m < num.size(); ++n, ++m)
{
int tmp_gap = num[m] - num[n];
if (tmp_gap > gap)
{
gap = tmp_gap;
}
}
//std::cout << gap << "\n";
return gap;
}
// Solution2 according to suggestion by leetcode
// This solution cost 44ms
typedef struct Bucket_S
{
int gap;
int max;
int min;
} Bucket_T;
void add2bluck(Bucket_T& bucket, int value)
{
if (bucket.max == -1)
{
bucket.max = value;
bucket.min = value;
}
else
{
if (bucket.max < value)
{
bucket.max = value;
}
else if (bucket.min > value)
{
bucket.min = value;
}
}
}
int getIndexInBucket(int min, int value, int min_gap)
{
return (value - min)/min_gap;
}
void caculateGapSelf(Bucket_T& bucket)
{
if (bucket.max != -1)
{
bucket.gap = bucket.max - bucket.min;
}
}
int solution_2(std::vector<int> &num)
{
if (num.size() < 2)
{
return 0;
}
int max = num[0];
int min = num[0];
for (unsigned int i = 1; i < num.size(); ++i)
{
if (num[i] > max)
{
max = num[i];
}
else if (num[i] < min)
{
min = num[i];
}
}
// std::cout << "Max: " << max <<" Min: "<< min << "\n";
int min_gap = (max - min)/(num.size() - 1);
if (min_gap == 0)
{
min_gap = 1;
}
// std::cout << "Min Gap:"<<min_gap<<"\n";
std::vector<Bucket_T> buckets;
int total_buckets = (max - min)/min_gap + 1;
for(unsigned int i = 0; i < total_buckets; ++i)
{
//std::cout<< i << "<<<";
Bucket_T b;
b.max = -1;
b.min = -1;
b.gap = -1;
buckets.push_back(b);
}
int max_gap = 0;
for (unsigned int i = 0; i < num.size(); ++i)
{
int index = getIndexInBucket(min, num[i], min_gap);
//std::cout<< index << " " << num[i] << "\n";
add2bluck(buckets[index], num[i]);
caculateGapSelf(buckets[index]);
if (buckets[index].gap > max_gap)
{
max_gap = buckets[index].gap;
}
}
for(unsigned int n = 0, m = 0; ;)
{
while (buckets[n].max == -1)
{
++n;
if (n >= buckets.size()-1)
{
return -1; // error condition
}
}
m = n + 1;
while (buckets[m].max == -1)
{
++m;
if (m > buckets.size()-1)
{
return -1;
}
}
int tmp_gap = buckets[m].min - buckets[n].max;
if (tmp_gap > max_gap)
{
max_gap = tmp_gap;
}
++n;
if ( n >= buckets.size()-1 || m >= buckets.size() - 1)
{
break;
}
}
return max_gap;
}
```