题解 | 最大间距

题干分析

题目给定我们一个无序整数数组,要求我们排序后返回相邻两元素间的最大差值. 并且题目要求我们在线性时间O(n),与线性额外空间O(n)下完成.

算法思路

题目明示进行排序,且要求在O(n)时间下完成,传统的排序几乎不行,因此我们需要考虑使用桶排或者基数排序,事实上也确实需要这么做. 排序完成后我们在遍历依次相减,最后从中找到最大间隔即可,两个过程时间复杂度均为O(n),符合要求.

实现代码

class Solution {
    void radixSort(vector<int> &arr, const int base = 10) {
        if (arr.empty()) return;

        // 辅助空间
        const int max_ = *ranges::max_element(arr); // 获取最大值
        const int n = static_cast<int>(arr.size());
        vector<int> out(n);

        // 对每一位进行桶排
        for (long long exp = 1; max_ / exp > 0; exp *= base) { // 使用long long防止溢出
            vector cnt(base, 0);

            // 计数
            for (int i = 0; i < n; ++i) {
                cnt[(arr[i] / exp) % base]++;
            }

            // 前缀和
            for (int i = 1; i < base; ++i) {
                cnt[i] += cnt[i - 1];
            }

            // 排序
            for (int i = n - 1; i >= 0; --i) {
                int tmp = (arr[i] / exp) % base;
                out[cnt[tmp] - 1] = arr[i];
                cnt[tmp]--;
            }

            arr = out;
        }
    }

public:
    int maximumGap(vector<int>& nums) {
        const int n = static_cast<int>(nums.size());
        if (n < 2) return 0;

        radixSort(nums); // 基数排序

        for (int i = n - 1; i > 0; --i) { // 逆序相减取间隔
            nums[i] -= nums[i - 1];
        }
        nums[0] = 0; // 首位置零

        return *ranges::max_element(nums);
    }
};

复杂度分析

• 时间复杂度: 基数排序共lgm趟,其中m为数组最大元素值,可近似为常数,因此时间复杂度为O(nlogm),其他共计O(n),总计为O(nlogm).
• 空间复杂度: 基数排序空间消耗为O(n)其他额外空间均为常数空间,总计为O(n).