Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Example 1:
Input: [1, 9, 2, 5]
Output: 4
Explanation: The sorted form is [1, 2, 5, 9], and the maximum gap is between 5 and 9.
Example 2:
Input: [1]
Output: 0
Explanation: The array contains less than 2 elements.
Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.
思路：
很多人用基数排序(桶排序)做这道题目, 时间复杂度接近线性, 当然比基于比较的快速排序等一众 O(nlogn) 的算法要优秀一些, 但是这道题可以有更巧妙的方法.
首先我们定义 maxNum 和 minNum 表示这个数组的最大/最小元素, N 表示这个数组元素的个数. 那么这个数组一共有 N - 1 个间距.
这 N - 1 个间距的平均值就是 avgGap = (maxNum - minNum) / (N - 1), 这个平均值也是答案的最小值. 因为这 N 个元素平均分配时, 最大的间距最小.
然后我们对这 N 个元素分类, 分类依据就是这个元素与 minNum 的间距是 avgGap 的多少倍. 为什么这样分类呢? 因为这样分类, 同一组内的元素的间距必然不会是最大间距.
这时我们要找的最大间距处于组与组之间, 即某一组里最小的元素与它上一组的最大的元素的间距的最大值. 因此, 我们只需要维护每一组里最小与最大的元素即可.
设定 maxNums 和 minNums 数组, maxNums[i] 表示原数组中与 minNum 的差为 avgGap 的 i 倍(向下取整)的最大的元素, 同理 minNums[i] 表示相同含义下的最小的元素.
然后我们遍历 maxNums, minNums, 将第 i 组的最小值 minNums[i] 与第 i - 1 组的最大值 maxNums[i - 1] 做差, 维护最大值就可以public class Solution
public class Solution {
/**
* @param nums: an array of integers
* @return: the maximun difference
*/
class Block {
public int min = Integer.MAX_VALUE;
public int max = Integer.MIN_VALUE;
}
/**
* @param nums: an array of integers
* @return: the maximun difference
*/
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int min = nums[0], max = nums[0];
for (int num : nums) {
min = Math.min(num, min);
max = Math.max(num, max);
}
if (max == min) {
return 0;
}
int N = nums.length;
Block[] blocks = new Block[N];
for (int i = 0; i < N; i++) {
blocks[i] = new Block();
}
int avgGap = (int) Math.ceil((double) (max - min) / (nums.length - 1));
for (int num : nums) {
if (num == min || num == max) {
continue;
}
int pos = (num - min) / avgGap;
blocks[pos].min = Math.min(num, blocks[pos].min);
blocks[pos].max = Math.max(num, blocks[pos].max);
}
int maxGap = 0;
int lastMax = min;
for (int i = 0; i < N; i++) {
if (blocks[i].min == Integer.MAX_VALUE || blocks[i].max == Integer.MIN_VALUE) {
continue ;
}
maxGap = Math.max(maxGap, blocks[i].min - lastMax);
lastMax = blocks[i].max;
}
maxGap = Math.max(maxGap, max - lastMax);
return maxGap;
}
}
原文：https://www.cnblogs.com/FLAGyuri/p/12078501.html