Medium

题目描述

给定一个整数数组 nums，返回数组排序后相邻两个元素之间的最大差值。如果数组包含的元素少于 2 个，则返回 0。

你必须编写一个在线性时间内运行并使用线性额外空间的算法。

示例 1：

输入：nums = [3,6,9,1]
输出：3
解释：排序后的数组是 [1,3,6,9]，其中 (3,6) 或 (6,9) 的最大差值都是 3。

示例 2：

输入：nums = [10]
输出：0
解释：数组包含的元素少于 2 个，因此返回 0。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解题思路

解题思路

题目要求在线性时间和线性空间内找到排序后相邻元素的最大间距，这意味着不能使用普通的排序算法（时间复杂度 O(nlogn)）。

方法一：基数排序（推荐）

基数排序是一种非比较排序算法，时间复杂度为 O(d×n)，其中 d 是数字的位数。对于 32 位整数，d 为常数，因此整体时间复杂度为 O(n)。

基数排序的核心思想是：

  1. 从最低位开始，对每一位进行计数排序
  2. 逐位处理，直到最高位
  3. 排序完成后遍历数组找最大间距

方法二：桶排序

利用抽屉原理，如果有 n 个数，那么排序后必然有 n-1 个间隔。如果将数值范围均匀分成 n-1 个桶，那么最大间距必然不会出现在桶内，而是出现在桶与桶之间。这样我们只需要记录每个桶的最小值和最大值，然后计算相邻非空桶之间的间距即可。

两种方法都能达到线性时间复杂度，基数排序实现相对简单，因此采用基数排序作为主要解法。

代码实现

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) return 0;
        
        // 基数排序
        radixSort(nums);
        
        // 找最大间距
        int maxGap = 0;
        for (int i = 1; i < nums.size(); i++) {
            maxGap = max(maxGap, nums[i] - nums[i-1]);
        }
        return maxGap;
    }
    
private:
    void radixSort(vector<int>& nums) {
        int maxVal = *max_element(nums.begin(), nums.end());
        
        // 对每一位进行计数排序
        for (int exp = 1; maxVal / exp > 0; exp *= 10) {
            countingSort(nums, exp);
        }
    }
    
    void countingSort(vector<int>& nums, int exp) {
        vector<int> output(nums.size());
        vector<int> count(10, 0);
        
        // 统计每个数字出现的次数
        for (int i = 0; i < nums.size(); i++) {
            count[(nums[i] / exp) % 10]++;
        }
        
        // 计算累积计数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i-1];
        }
        
        // 构建输出数组
        for (int i = nums.size() - 1; i >= 0; i--) {
            output[count[(nums[i] / exp) % 10] - 1] = nums[i];
            count[(nums[i] / exp) % 10]--;
        }
        
        // 复制回原数组
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = output[i];
        }
    }
};

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        
        # 基数排序
        self.radix_sort(nums)
        
        # 找最大间距
        max_gap = 0
        for i in range(1, len(nums)):
            max_gap = max(max_gap, nums[i] - nums[i-1])
        
        return max_gap
    
    def radix_sort(self, nums):
        max_val = max(nums)
        
        # 对每一位进行计数排序
        exp = 1
        while max_val // exp > 0:
            self.counting_sort(nums, exp)
            exp *= 10
    
    def counting_sort(self, nums, exp):
        n = len(nums)
        output = [0] * n
        count = [0] * 10
        
        # 统计每个数字出现的次数
        for i in range(n):
            index = (nums[i] // exp) % 10
            count[index] += 1
        
        # 计算累积计数
        for i in range(1, 10):
            count[i] += count[i-1]
        
        # 构建输出数组
        for i in range(n-1, -1, -1):
            index = (nums[i] // exp) % 10
            output[count[index] - 1] = nums[i]
            count[index] -= 1
        
        # 复制回原数组
        for i in range(n):
            nums[i] = output[i]

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums.Length < 2) return 0;
        
        // 基数排序
        RadixSort(nums);
        
        // 找最大间距
        int maxGap = 0;
        for (int i = 1; i < nums.Length; i++) {
            maxGap = Math.Max(maxGap, nums[i] - nums[i-1]);
        }
        return maxGap;
    }
    
    private void RadixSort(int[] nums) {
        int maxVal = nums.Max();
        
        // 对每一位进行计数排序
        for (int exp = 1; maxVal / exp > 0; exp *= 10) {
            CountingSort(nums, exp);
        }
    }
    
    private void CountingSort(int[] nums, int exp) {
        int n = nums.Length;
        int[] output = new int[n];
        int[] count = new int[10];
        
        // 统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            count[(nums[i] / exp) % 10]++;
        }
        
        // 计算累积计数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i-1];
        }
        
        // 构建输出数组
        for (int i = n - 1; i >= 0; i--) {
            output[count[(nums[i] / exp) % 10] - 1] = nums[i];
            count[(nums[i] / exp) % 10]--;
        }
        
        // 复制回原数组
        for (int i = 0; i < n; i++) {
            nums[i] = output[i];
        }
    }
}

var maximumGap = function(nums) {
    if (nums.length < 2) return 0;
    
    // 基数排序
    radixSort(nums);
    
    // 找最大间距
    let maxGap = 0;
    for (let i = 1; i < nums.length; i++) {
        maxGap = Math.max(maxGap, nums[i] - nums[i-1]);
    }
    return maxGap;
};

function radixSort(nums) {
    const maxVal = Math.max(...nums);
    
    // 对每一位进行计数排序
    for (let exp = 1; Math.floor(maxVal / exp) > 0; exp *= 10) {
        countingSort(nums, exp);
    }
}

function countingSort(nums, exp) {
    const n = nums.length;
    const output = new Array(n);
    const count = new Array(10).fill(0);
    
    // 统计每个数字出现的次数
    for (let i = 0; i < n; i++) {
        count[Math.floor((nums[i] / exp) % 10)]++;
    }
    
    // 计算累积计数
    for (let i = 1; i < 10; i++) {
        count[i] += count[i-1];
    }
    
    // 构建输出数组
    for (let i = n - 1; i >= 0; i--) {
        const index = Math.floor((nums[i] / exp) % 10);
        output[count[index] - 1] = nums[i];
        count[index]--;
    }
    
    // 复制回原数组
    for (let i = 0; i < n; i++) {
        nums[i] = output[i];
    }
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型基数排序解法
时间复杂度O(d×n)，其中 d 是数字的最大位数，对于 32 位整数 d 为常数，因此为 O(n)
空间复杂度O(n)

相关题目