专栏首页mathorLeetCode164. 最大间距

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 条评论
登录 后参与评论

相关文章

  • LeetCode216. 组合总和 III

     简单的dfs问题,标记每一个数用没用过,没用过就用,v[i]=true,k--,n-=i,然后回溯就只需要将他们还原就行,注意这里是不能重复选,因此下一...

    mathor
  • 第六届蓝桥杯决赛B组C/C++——关联账户

    mathor
  • LeetCode77. 组合

     常规dfs题,首先在dfs函数中判断边界条件,因为只要取到k个数就够了,所以边界条件当k用完,也就是k==0就应该return了。然后再看dfs函数内部的实现...

    mathor
  • 【Gym - 100796C 】Minimax Tree

    BUPT2017 wintertraining(15) #7FMinimax Tree

    饶文津
  • 浙大版《C语言程序设计(第3版)》题目集 练习5-2 找两个数中最大者

    C you again 的博客
  • 蓝桥杯之移动距离

    移动距离 X星球居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为1,2,3… 当排满一行时,从下一行相邻的楼往反方向排号。 比如:当小区...

    用户4492257
  • 手把手教你写linux系统下贪吃蛇(二)

    创建线程后把第一篇用到的refresh()函数都删除,不然因为缓存区的原因产生乱码

    用户2965768
  • AtCoder Beginner Contest 103

    首先我们发现,对于每个$a_i$,我们都可以构造一个数使得$x \pmod {a_i} = a_i - 1$

    attack
  • 2006北京市小学生程序设计友谊赛详细答案

    分析: 祖冲之密率355/113是圆周率pi的近似值。 注意: 本题第一个输入输出样例有误。输入为4时,输出应为5。 算法实现:

    海天一树
  • hihoCoder 1700 相似颜色

            题目链接: http://hihocoder.com/problemset/problem/1700

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券