在无序数组中，经过排序后，找相邻元素的最大差值（O(N)）

一个无序数组，如何求出该数组排序后的任意相邻元素的最大差值，要求时间和空间复杂度尽可能低。

常规操作： 利用快排或堆排堆数组进行排序，时间复杂度为O(NlogN)， 比较排序后的数组，两个相邻元素的最大差值。优化的方法：利用计数排序(当最大值和最小值相差较大时，有大的局限性)， 最大差值为新数组中连续出现0值的次数再加上1。简单方式： 利用桶排序，该方法不需要像标准桶排序一样给每一个桶内部进行排序，只需要记录桶内的最大值和最小值即可，时间复杂度稳定在O(N)。 package kyrie.com; /** * @program: Aglorithm * @Author: Kyrie * @Description: */ public class Code06_Each_Max_Difference { public static int getMaxDiff(int[] arr){ //找数组的最大值和最小值 int array_min = Integer.MAX_VALUE; int array_max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { if(arr[i] > array_max){ array_max = arr[i]; } if(arr[i] < array_min){ array_min = arr[i]; } } int d = array_max - array_min; if(d == 0) //所有元素相同，直接返回0 return 0; //创建桶 int bucketNum = arr.length; Bucket[] buckets = new Bucket[bucketNum]; //初始化桶 for (int i = 0; i < bucketNum; i++) { buckets[i] = new Bucket(); } //遍历数组元素 for (int i = 0; i < arr.length ; i++) { int index = (arr[i] - array_min) * (bucketNum - 1) / d; //确定该元素对应桶的索引 if(buckets[index].min == null || buckets[index].min > arr[i]){ buckets[index].min = arr[i]; } if(buckets[index].max == null || buckets[index].max < arr[i]){ buckets[index].max = arr[i]; } } //遍历桶，找到最大差值 int maxDiff = 0; int left = buckets[0].max; //左桶的最大值 for (int i = 0; i < bucketNum; i++) { if(buckets[i].min == null){ continue; } if (buckets[i].min - left > maxDiff){ maxDiff = buckets[i].min - left; } left = buckets[i].max; } /* for (int i = 0; i < bucketNum ; i++) { System.out.println(buckets[i].min); } */ return maxDiff; } public static void main(String[] args) { int[] array = {2, 6, 3, 4, 5, 10, 9}; System.out.println(getMaxDiff(array)); } } class Bucket{ Integer min; Integer max; }