欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

D-LeetCode164-最大间距

程序员文章站 2022-04-04 10:05:06
...

题目

给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。

如果数组元素个数小于 2,则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0。
说明:

你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

思路

https://blog.csdn.net/zxzxzx0119/article/details/82889998

D-LeetCode164-最大间距

代码

class Solution {
    public int maximumGap(int[] nums) {
        if(nums.length<2){
            return 0;
        }
        
        // 求出nums[]最大值、最小值
        int max=nums[0];
        int min=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]>max){
                max=nums[i];
            }
            if(nums[i]<min){
                min=nums[i];
            }
        }
        if(max==min){
            return 0;
        }
        
        // 计算区间的长度
        int qujian=0;
        if( (max-min)%nums.length==0 ){
            qujian=(max-min)/nums.length;
        }else{
            qujian=(max-min)/nums.length+1;
        }
        
        // 多少个区间
        int[] tongsmax=new int[nums.length+1];
        int[] tongsmin=new int[nums.length+1];
        boolean[] tongshave=new boolean[nums.length+1];
        
        // nums[]放入对应的区间
        for(int i=0;i<nums.length;i++){
            //nums[i]属于哪个区间
            int index=(nums[i]-min)/qujian;
            if(index>=tongshave.length){
                index=tongshave.length-1;
            }
            
            if(tongshave[index]==false){
                tongsmax[index]=nums[i];
                tongsmin[index]=nums[i];
                tongshave[index]=true;
            }else{
                if(nums[i]>tongsmax[index]){
                    tongsmax[index]=nums[i];
                }
                if(nums[i]<tongsmin[index]){
                    tongsmin[index]=nums[i];
                }
            }
        }

        // 上个区间最大值与本区间最小值的差值
        int res=0;
        int premax=tongsmax[0];
        for(int i=1;i<tongshave.length;i++){
            if(!tongshave[i]){
                continue;
            }
            if ((tongsmin[i]-premax)>res){
                res=tongsmin[i]-premax;
                
            }
            premax=tongsmax[i];
        }
        
        return res;
    }
}