相邻两数的差值

一、题目

给定一个数组，求如何排序之后，相邻两数的最大差值。要求时间复杂度 O(N)，且要求不能用非基于比较的排序

二、分析

我们一般的排序的时间复杂度最小为 N*logN。这里我们假设有 N 个数，我们定义 N+1 长度的容器，相当于 N+1 个桶。先求出这 N 个数的最大值和最小值。然后将这些数等分为 N+1 份，分布在这 N+1 个桶中。

此时必然有数的最小值存在于最左边的桶，数的最大值存在于最右边的桶。并且一定会有一个空桶，因为 N 个桶有 N+1 个桶。

每个桶保存两个数，当前桶所表示的范围中的最大值和最小值。那么最终相邻两数的最大差值一定来自于两桶之间的差值，也就是左边桶的最大值和相邻右边桶的最小值。

为什么要 N+1 个桶呢？为了就是去掉那些平凡解。这些桶中相邻差值，要么来自于桶内、要么来自于相邻桶。增加一个桶相当于去掉了桶内的解，让相邻桶的差值一定大于桶内元素的差值。增加一个桶相当于缩小了一个桶本应该表示的范围。

struct Elem {
    int max{INT32_MIN};
    int min{INT32_MAX};
    bool is_empty{true};
};

class Solution {
public:
    int get_max_gap(const std::vector<int>& arr) {
        if (arr.empty()) {
            return 0;
        }
        int max = INT32_MIN;
        int min = INT32_MAX;
        for (int i = 0; i < arr.size(); i++) {
            max = std::max(max, arr[i]);
            min = std::min(min, arr[i]);
        }
        if (min == max) {
            return 0;
        }
        std::vector<Elem> nums;
        nums.resize(arr.size()+1);
        for (int i = 0; i < arr.size(); i++) {
            int pos = (arr[i]-min) * arr.size() / (max-min);
            nums[pos].max = std::max(nums[pos].max, arr[i]);
            nums[pos].min = std::min(nums[pos].min, arr[i]);
            nums[pos].is_empty = false;
        }
        int res = INT32_MIN;
        for (int i = 0, j = 1; i < nums.size()-1 && j < nums.size();) {
            if (nums[i].is_empty == true) {
                i++;
                continue;
            }
            if (nums[j].is_empty == true) {
                j++;
                continue;
            }
            res = std::max(res, nums[j].min - nums[i].max);
            i++;
            j++;
        }
        return res;
    }
};