题目

代码分析

是对桶排序思想的应用，最重要的代码是就是判断当前的元素应该放入到哪一个桶中。为了防止溢出，首先都是long型然后再转化成int型。其次就是找到空闲的桶以及空闲的桶的两边不是空的桶。

代码实现

public static int maximumGap(int[] nums) {

        int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++)
        {
            min=Math.min(min,nums[i]);
            max=Math.max(max,nums[i]);
        }
        if(min==max) return 0;
        System.out.println(min+" "+max);
        int[] mins=new int[nums.length];
        int[] maxs=new int[nums.length];
        boolean[] isNotEmpty=new boolean[nums.length];
        for(int i=0;i<nums.length;i++)
        {
            int index=findBucketIndex(nums[i],min,max,nums.length-1);
            System.out.println(index);
            mins[index]=!isNotEmpty[index]?nums[i]:Math.min(mins[index],nums[i]);
            maxs[index]=!isNotEmpty[index]?nums[i]:Math.max(maxs[index],nums[i]);
            isNotEmpty[index]=true;
        }
        max=Integer.MIN_VALUE;
        //找到空桶然后计算
        int index=0;
        int start=-1;
        while(index<nums.length)
        {
            if(!isNotEmpty[index]&&start==-1)
            {
                start=index-1;
            }else if(isNotEmpty[index]&&start!=-1)
            {
                max=Math.max(max,mins[index]-maxs[start]);
                start=-1;
            }
            index++;
        }

        return max;
    }

    public static int findBucketIndex(long cur,long min,long max,long len)
    {
        return (int)((cur-min)*len/(max-min));
    }

学习情况

1次