LeetCode164. 最大间距

题目链接: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));
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从零开始学 Web 前端

05 - JavaSE之数组

17440
来自专栏公众号_薛勤的博客

让你一看就懂的快速排序算法(Java)

你也许会被快速排序的文章弄得迷迷糊糊,其实大体上去看,快速排序就一步:找个数做基准数,把小于它的数移到它左边,把大于它的数移到它右边。这句话是核心。然后我们只需...

12720
来自专栏海天一树

图的深度优先搜索

图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

12920
来自专栏尾尾部落

[剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

11020
来自专栏Python爱好者

Java基础笔记05

18180
来自专栏云霄雨霁

排序----插入排序

15800
来自专栏瓜大三哥

Matlab基本运算3

字符串指的是1xn的字符数组。单个字符是按照unicode编码存储的,每个字符占两个字节 ? 在matlab中,只要用(‘)将需要设定的字符串括起来。 disp...

22360
来自专栏mathor

波兰表达式

25740
来自专栏ACM算法日常

分割排序(排序)- HDU 1106

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整...

9910
来自专栏赵俊的Java专栏

最长上升连续子序列

19040

扫码关注云+社区

领取腾讯云代金券