LeetCode 164. 最大间距
原题链接
困难
作者:
bruce
,
2021-01-09 12:00:38
,
所有人可见
,
阅读 230
class Solution {
public:
struct bucket
{
int min, max;
bool used;
bucket() : min(INT_MAX), max(INT_MIN), used(false){};
};
int maximumGap(vector<int> &nums)
{
int n = nums.size();
int Min = INT_MAX, Max = INT_MIN;
for (auto x : nums) // 求这个区间的最大值和最小值
{
Min = min(x, Min);
Max = max(x, Max);
}
if (n < 2 || Max == Min)
return 0;
vector<bucket> r(n - 1); // 区间数
int len = (Max - Min + n - 2) / (n - 1); // 这一步没有看懂
for (auto x : nums) // 找到每一个区间的最小值和最大值
{
if (x == Min)
continue;
int k = (x - Min - 1) / len;
r[k].used = true;
r[k].min = min(r[k].min, x);
r[k].max = max(r[k].max, x);
}
int res = 0;
for (int i = 0, last = Min; i < n - 1; i++)
{
if (r[i].used)
{
res = max(res, r[i].min - last);
last = r[i].max;
}
}
return res;
}
};