solution.md

# 最大间距

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

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

<p><strong>示例&nbsp;1:</strong></p>

<pre><strong>输入:</strong> [3,6,9,1]
<strong>输出:</strong> 3
<strong>解释:</strong> 排序后的数组是 [1,3,6,9]<strong><em>, </em></strong>其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。</pre>

<p><strong>示例&nbsp;2:</strong></p>

<pre><strong>输入:</strong> [10]
<strong>输出:</strong> 0
<strong>解释:</strong> 数组元素个数小于 2，因此返回 0。</pre>

<p><strong>说明:</strong></p>

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

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    int res;
    vector<int> nums = {3, 6, 9, 1};
    res = sol.maximumGap(nums);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int maximumGap(vector<int> &nums)
    {
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[mid + 1])
                l = mid + 1;
            else
                r = mid;
        }
        return r;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int maximumGap(vector<int> &nums)
    {
        if (nums.size() < 2)
            return 0;
        if (nums.size() == 2)
            return abs(nums[1] - nums[0]);
        int maxn = 0;
        int minn = INT_MAX;
        for (int i = 0; i < nums.size(); i++)
            maxn = max(maxn, nums[i]);
        for (int i = 0; i < nums.size(); i++)
            minn = min(minn, nums[i]);
        if (maxn == minn)
            return 0;
        int size = (maxn - minn) / nums.size();
        if (size < 1)
            size = 1;
        int num = (maxn - minn) / size + 1;
        vector<int> nummax(num, 0);
        vector<int> nummin(num, maxn);
        nummin[0] = minn;
        nummax[0] = minn;
        nummax[num - 1] = maxn;
        nummin[num - 1] = maxn;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == maxn || nums[i] == minn)
                continue;
            int qnum = (nums[i] - minn) / size;
            nummax[qnum] = max(nummax[qnum], nums[i]);
            nummin[qnum] = min(nummin[qnum], nums[i]);
        }
        for (int i = 0; i < nummin.size(); i++)
        {
            if (nummax[i] == 0 && nummin[i] == maxn)
            {
                nummax.erase(nummax.begin() + i);
                nummin.erase(nummin.begin() + i);
                i--;
            }
        }
        int res = 0;
        for (int i = 1; i < nummax.size(); i++)
        {
            res = max(res, nummin[i] - nummax[i - 1]);
        }
        return res;
    }
};
```

### B

```cpp
class Solution
{
public:
    int maximumGap(vector<int> &nums)
    {
        if (nums.empty())
            return 0;
        int mx = INT_MIN, mn = INT_MAX, n = nums.size();
        for (int a : nums)
        {
            mx = max(a, mx);
            mn = min(a, mn);
        }
        int size = (mx - mn) / n + 1;
        int bucket_nums = (mx - mn) / size + 1;
        vector<int> bucket_min(bucket_nums, INT_MAX);
        vector<int> bucket_max(bucket_nums, INT_MIN);
        set<int> s;
        for (int a : nums)
        {
            int indx = (a - mn) / size;
            bucket_max[indx] = max(bucket_max[indx], a);
            bucket_min[indx] = min(bucket_min[indx], a);
            s.insert(indx);
        }
        int pre = 0, ans = 0;
        for (int i = 1; i < bucket_nums; ++i)
        {
            if (!s.count(i))
                continue;
            int t = bucket_min[i] - bucket_max[pre];
            ans = max(ans, t);
            pre = i;
        }
        return ans;
    }
};
```

### C

```cpp
class Solution
{
public:
    static bool cmp(const int &a, const int &b)
    {
        return a < b;
    }
    int maximumGap(vector<int> &nums)
    {
        if (nums.size() <= 1)
            return 0;
        sort(nums.begin(), nums.end(), cmp);
        int maxgap = 0;
        for (int i = 1; i < nums.size(); i++)
        {
            maxgap = max(maxgap, nums[i] - nums[i - 1]);
        }
        return maxgap;
    }
};
```