讨论/《高频算法实战》 - 最大间距/
《高频算法实战》 - 最大间距
共 4 个回复
class Solution {
    public int maximumGap(int[] nums) {
        if(nums.length<2)return 0;
        if(nums.length==2)return Math.abs(nums[0]-nums[1]);
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int k:nums){
            min = Math.min(min,k);
            max = Math.max(max,k);
        }
        int d = (max-min)/(nums.length-1)+1;// 确定间距很重要
        if(d==0)return nums[0];
        int backets[][] = new int[nums.length][2];
        //backets[i][0]存放该桶的最大元素
        //backets[i][1]存放该桶的最小元素
        for(int i =0;i<backets.length;i++)
        Arrays.fill(backets[i],-1);
        for(int i = 0;i<backets.length;i++){
            int index = Math.min(backets.length-1,(nums[i]-min)/d);//确定桶下标
            if(backets[index][0]==-1){
                backets[index][0] = nums[i];
            }else{
                backets[index][0] = Math.max(backets[index][0],nums[i]);
            }
            if(backets[index][1]==-1){
                backets[index][1] = nums[i];
            }else{
                backets[index][1] = Math.min(backets[index][1],nums[i]);
            }
        }
        int res = 0;
        for(int i = 0;i<backets.length-1;i++){
            int m = backets[i][0];
            int j = i+1;
            while(j<backets.length){
                if(backets[j][0]==-1)j++;//如果该桶不存在元素则跳过
                else{
                    res =Math.max(res,backets[j][1]-m);
                    break;
                }
            }
            i = j-1;//这一步必须要有,否则外层循坏无法遍历到每一个有数存在的桶
        }
        return res;
    }
}
3
class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return 0
        if len(nums) == 2:
            return max(nums)-min(nums)
        d = (max(nums)-min(nums))//(len(nums)-1)+1
        if d == 0:
            return nums[0]
        baskets = [[] for _ in range(len(nums)-1)]
        for i in range(len(nums)):
            place = min(len(nums)-1,(nums[i]-min(nums))//d)
            baskets[place].append(nums[i])
        distant = 0
        for j in range(len(nums)-2):
            if baskets[j]:
                for k in range(j+1,len(nums)-1):
                    if baskets[k]:
                        distant = max(distant,min(baskets[k])-max(baskets[j]))
                        break
                    else:
                        continue
        return distant

注意几个特殊情况:

  1. 当nums长度正好为2或者小于2
  2. 当两个不空桶中有空桶时
2

桶排序+Python

def maximumGap(nums):
    if len(nums) < 2:
        return 0
    max_num = max(nums)
    min_num = min(nums)
    bucket_len = max(1, (max_num-min_num)//(len(nums)-1))
    bucket_num = (max_num-min_num) // bucket_len +1
    bucket = [[] for _ in range(bucket_num)]
    outcome = 0
    for a in nums:
        pos = (a - min_num) // bucket_len
        bucket[pos].append(a)

    pre_max = float('inf')
    for i in range(len(bucket)):
        if bucket[i] and pre_max != float('inf'):
            outcome = max(outcome, min(bucket[i])-pre_max)
        if bucket[i]:
            pre_max = max(bucket[i])
    return outcome
1

java

class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if( n==1 ) return 0;
        int[] min = new int[n+1]; // 第i个桶的最小值
        int[] max = new int[n+1]; // 第i个桶的最大值
        int vmin = Integer.MAX_VALUE,vmax=-1;
        // 遍历一遍找最大最小值
        for(int i=0;i<n;i++)
        {
            if( vmin>nums[i] ) vmin = nums[i];
            if( vmax<nums[i] ) vmax = nums[i];
        }
        for( int i=1;i<=n;i++ ){ // 初始化桶的最大值,最小值
            min[i] = Integer.MAX_VALUE;
            max[i] = -1;
        }
        int d = (vmax-vmin)/(n-1) + ( (vmax-vmin)%(n-1)==0?0:1 );
        if( d==0 ) return 0;
        for(int i=0;i<n;i++){
            int cnt = (nums[i]-vmin)/d+1; // 看nums[i]位于第几个桶
            if( min[cnt]>nums[i] ) min[cnt] = nums[i];
            if( max[cnt]<nums[i] ) max[cnt] = nums[i];
        }
        for(int i=1;i<n;i++){
            if( max[i+1]==-1 ) // 第i+1个桶没有数
                min[i+1] = max[i+1] = max[i];
        }
        int ans = -1;
        for(int i=1;i<n;i++){
            if(min[i+1]-max[i]>ans)
                ans = min[i+1]-max[i]; 
        }
        return ans;
    }
}