各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

LeetCode164. 最大间距

August 7, 2018 • Read: 454 • LeetCode

题目链接:Leetcode164

题解

这道题用到了桶排序的思想,但是跟排序没啥关系,思路是这样的,数组中有n个元素,那么就构建n+1个桶,桶的属性有三个,最大值最小值以及是否为空。桶的下标从0到n,然后遍历一遍数组,将其中最小值放到0号桶的位置,最大值放到n号桶的位置,这样的话1~n-1号桶应该放什么数就很清楚了,然后再遍历一遍数组,将其中的所有元素放至应该放到的桶内,并且维护桶的属性,即每个桶的最大值和最小值以及是否为空

最后遍历一遍桶,用当前桶的最小值减去上一个桶的最大值,找到最大的那个数即是答案

代码

class Solution {
    class Bucket {
        int max,min;
        boolean hasNum;
    }
    public int maximumGap(int[] nums) {
        int len = nums.length;
        Bucket[] bucket = new Bucket[len + 1];
        for(int i = 0;i <= len;i++)
            bucket[i] = new Bucket();
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i:nums) {
            max = Math.max(max,i);
            min = Math.min(min,i);
        }
        if(max == min) 
            return 0;
        for(int i = 0;i < len;i++) {
            int idx = put(nums[i],max,min,len);
            if(!bucket[idx].hasNum) {
                bucket[idx].max = nums[i];
                bucket[idx].min = nums[i];
                bucket[idx].hasNum = true;
            } else {
                bucket[idx].max = Math.max(bucket[idx].max,nums[i]);
                bucket[idx].min = Math.min(bucket[idx].min,nums[i]);
            }
        }
        int res = 0;
        int lastMax = bucket[0].max;
        int i = 1;
        for(;i <= len;i++) {
            if(bucket[i].hasNum) {
                res = Math.max(res,bucket[i].min - lastMax);
                lastMax = bucket[i].max;
            }
        }
        return res;
    }
    public static int put(long num,long max,long min,long len) {//计算放在几号桶
        return (int)((num - min) * len / (max - min));
    }
}
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment