题目

有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。

测试样例：[1,2,5,4,6],5
返回：2

思路

首先题目中明确说明需要对数组进行排序，同时又要求时间复杂度是O(n)，显然不能用基于比较的排序算法进行排序。自然地我们会想到桶排序，但是不是普通的计数排序，因为数字的范围不定，不可能用上亿个桶来存储。为了减少使用的桶的数量，那就必须增大每个桶的宽度。基于这个思路可以得出解题步骤如下。
设我们需要N+1个桶来存储N个数，找出N个数中的最大值max和最小值min，将[min,max]区间划分为N个桶，每个桶的宽度是(max-min)/N。在遍历数组的过程中将数字放到相应的桶中，由于我们用N+1个桶来存放N个数，所以必然会出现空桶，显然空桶两侧的数字的差值是大于桶内的数字的差值的，所以我们需要找到空桶两侧的桶，用左侧的桶的最大值和右侧的桶的最小值进行比较。

以{2,3,7,9,8,1,4}为例。

图片来自牛客网

import java.util.*;
public class Gap {
  
    private int bucketNum;
    private int minus;
    private int min;

    public int maxGap(int[] A, int n) {
        bucketNum = n;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : A) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        this.min = min;
        minus = (max - min);
        int[] mins = new int[n + 1];
        int[] maxs = new int[n + 1];
        boolean[] hasNum = new boolean[n + 1];
        int bucketID = 0;
        int i = 0;
        for (; i < n; i++) {
            bucketID = bucket(A[i]);
            mins[bucketID] = hasNum[bucketID] ? Math.min(mins[bucketID], A[i]) : A[i];
            maxs[bucketID] = hasNum[bucketID] ? Math.max(maxs[bucketID], A[i]) : A[i];
            hasNum[bucketID] = true;
        }

        int maxGap = 0;
        int lastMax = 0;
        
        i=0;
        while (i < n + 1) {
            //找到一个空桶,记录下前一个桶的最大值
            while (i < n + 1 && hasNum[i]) {
                i++;
            }
            if (i == n + 1) break;
            lastMax = maxs[i - 1];
            //找到下一个非空桶，记录该桶的最小值
            while (i < n + 1 && !hasNum[i]) {
                i++;
            }
            if (i == n + 1) break;
            maxGap = Math.max(maxGap, mins[i] - lastMax);
        }
        return maxGap;
    }

    private int bucket(int num) {
        return (int) ((num - min) * bucketNum / minus);
    }
}