【算法】相邻最大差值---MapleYe

问题描述

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N) 例子： 5,9,8,3,15 那么排序后的数，3,5,8,9,15，因此相邻最大差值为15-9=6

解题思路

由于时间复杂度要求为O(N)，因此快排，归并排序都不能使用了。这里我们需要借助桶排序的思想：

1）找出数组的最大值max和最小值min 2）将区间均等的划分为 N + 1份，即有N + 1个桶。由于只有N个数，那么必有一个桶为空桶 3）遍历数组，将所有数入桶，并记录每一个桶的max和min 4）不需要考虑桶内数的差值，因为它都不会大于空桶两边的桶的差值 5）遍历每一个桶，由于每个桶只存该区间的max和min，因此前桶的max和后桶的min必相邻。 依次比较每两非空桶，即后桶的min减去前桶的max 的差值，即可获得最大的差值

实现代码 public static int maxGap(int[] nums) { if (nums == null || nums.length < 2) { return 0; } // 1）找出数组的最大值max和最小值min int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < nums.length; i++) { if (nums[i] > max) { max = nums[i]; } if (nums[i] < min) { min = nums[i]; } } // 区间内数字全相等 if (min == max) { return 0; } // 2）将区间均等的划分为 N + 1份，即有N + 1个桶 // 3）遍历数组，将所有数入桶，并记录每一个桶的max和min int len = nums.length; boolean[] hasNum = new boolean[len + 1]; int[] maxNums = new int[len + 1]; int[] minNums = new int[len + 1]; int bid = 0; for(int i = 0; i < len; i++) { bid = getBucketId(max, min, len, nums[i]); maxNums[bid] = hasNum[i] ? Math.max(maxNums[bid], nums[i]) : nums[i]; minNums[bid] = hasNum[i] ? Math.min(minNums[bid], nums[i]) : nums[i]; hasNum[bid] = true; } int res = 0; int lastMax = maxNums[0]; // 4）不需要考虑桶内数的差值，因为它都不会大于空桶两边的桶的差值 // 遍历每一个桶，由于每个桶只存该区间的max和min，因此前桶的max和后桶的min必相邻。 // 依次比较每两非空桶，即后桶的min减去前桶的max 的差值，即可获得最大的差值 for(int i = 0; i <= len; i++) { if (hasNum[i]) { res = Math.max(res, minNums[i] - lastMax); lastMax = maxNums[i]; } } return res; } /// max最大值，min最小值，划分多少等分，num数值，返回num落在哪个区间的index /// long是为了防溢出 public static int getBucketId(long max, long min, long len, long num) { // 计算num占了多少份区间 // 一份为 (max - min) / len return (int)((num - min) * len / (max - min)); } ---来自腾讯云社区的---MapleYe