来自左神初级算法地一道高频题。
基本思路:
(1)n为数组的长度,准备n+1个桶,如果桶里有元素,则标记这个桶为true, 同时每个桶里只统计最大值和最小值。
(2)设三个数组,长度均为n+1,分别表示每个桶里是否有元素,最大值和最小值
(3)每个桶去寻找左边的非空桶,本桶的最小值减去左边桶的最大值,更新一个全局变量res,为最终解。
public static int maxGap(int[] nums){ if(nums == null || nums.length < 2) return 0; int len = nums.length; int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for(int i = 0; i < len; i++) { min = Math.min(min, nums[i]); max = Math.max(max, nums[i]); } if(min == max) return 0; boolean[] hasNum = new boolean[len + 1]; int[] maxs = new int[len + 1]; int[] mins = new int[len + 1]; int bid = 0; for(int i= 0; i < len; i++){ bid = bucket(nums[i], len, min, max); //nums[i]在哪一个桶中 mins[bid] = hasNum[i] ? Math.min(mins[bid], nums[i]) : nums[i]; maxs[bid] = hasNum[i] ? Math.max(maxs[bid], nums[i]) : nums[i]; hasNum[bid] = true; } int res = 0; int lastMax = maxs[0]; int i = 1; for(; i <= len; i++){ if(hasNum[i]){ res = Math.max(res, mins[i] - lastMax); lastMax = maxs[i]; } } return res; } //确定一个数应该去几号桶 public static int bucket(long num, long len, long min, long max){ return (int)((num - min) * len / (max - min)); }