LeetCode修炼之路----------164. 最大间距

164. 最大间距

题目如下：

解题代码与解析：

public int maximumGap(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int n = nums.length;
        int min = nums[0];
        int max = nums[0];
        //找出最大值、最小值
        for (int i = 1; i < n; i++) {
            min = Math.min(nums[i], min);
            max = Math.max(nums[i], max);
        }
        if(max - min == 0) {
            return 0;
        }

        /**
         *     总长度为max - min这么长，因为max和min在长度即范围的两端，所以在范围内的数
         * 有n - 2 个，n为数组长度；如果当做n - 1 个数来瓜分范围长度，那么，肯定会有一段是空的，
         * 而空段的前后两个值的比较将会是最大间距；由于段的范围是由总长度/(n-1)得来的，
         * 那么段得范围将是个区间来的，那么在一段中可以有多个数；  段范围 = 总长度 / （n - 1）
         *     为何最大间距不在段中，因为段中最大的距离也不过是段长度-1(最右-最左)，而空段的
         * 前后距离最小也是段长度，因此最大距离不会出现在同一段中即不会在同一个桶中。
         *     以min为起始点，max为终点，那么所有元素都将在它们的范围中，又由于该范围分段了，
         * 所以元素 - min将求的 距离min多远，然后再除以段长度就可以求得所归位置    
         *    位置 = （元素 - min） / 段范围
         */
        int interval = (int) Math.ceil((double)(max - min) / (n - 1));

        //每个箱子里数字的最小值和最大值
        int[] bucketMin = new int[n - 1];
        int[] bucketMax = new int[n - 1];

        //最小值初始为 Integer.MAX_VALUE
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        //最小值初始化为 -1，因为题目告诉我们所有数字是非负数
        Arrays.fill(bucketMax, -1);

        //考虑每个数字
        for (int i = 0; i < nums.length; i++) {
            //当前数字所在箱子编号
            int index = (nums[i] - min) / interval;

            //由于我们是在min和max中间范围进行分段分桶的，所以min和max不考虑
            if(nums[i] == min || nums[i] == max) {
                continue;
            }
            //更新当前数字所在箱子的最小值和最大值
            bucketMin[index] = Math.min(nums[i], bucketMin[index]);
            bucketMax[index] = Math.max(nums[i], bucketMax[index]);
        }

        int maxGap = 0;
        //min 看做第 -1 个箱子的最大值
        int previousMax = min;
        /**
         *     由于分段的时候，第一个段肯定是和min组成的即左边会是min；而一个段的左边是前一个段
         * 的右边即它的最大那么可把min看成第一段的前面段的最大值   
         *     最大间距 = 后一段的最小值 - 前一段的最大值
         *     一定要注意当非均匀递增的情况，那么由于会多出来一段，那么最大间距肯定是由空端的
         * 前后组成的左右边的距离最大
         */
        //从第 0 个箱子开始计算
        for (int i = 0; i < n - 1; i++) {
            //最大值是 -1 说明箱子中没有数字，直接跳过
            if (bucketMax[i] == -1) {
                continue;
            }

            //当前箱子的最小值减去前一个箱子的最大值
            maxGap = Math.max(bucketMin[i] - previousMax, maxGap);
            previousMax = bucketMax[i];
        }
        /**
         *     由于最大值是没有算进分段中的，所有还要比较一下最大值前面的第一个非空桶的最大值
         * 与整个数组中的最大值即最右边直接的距离
         */
        //最大值可能处于边界，不在箱子中，需要单独考虑
        maxGap = Math.max(max - previousMax, maxGap);
        return maxGap;
    }

结果如下：

谢谢阅读，如有不对之处请指出！