題目:計算數(shù)組中相鄰數(shù)據(jù)的最大差值
要求時間復雜度為 O(N)
算法思想:

利用桶的思想

• 1.假設(shè)數(shù)組長度為N,那么我們做N+1個桶,即可以完全放下數(shù)組
• 2.首先我們求出數(shù)組中的最大值和最小值,利用這個可對數(shù)組中數(shù)據(jù)分桶
• 3.將數(shù)組中的數(shù)據(jù)放入桶中,桶中只保留插入的最大值和最小值
• 4.
  關(guān)于紅字部分解讀圖:

算法代碼部分

package com.day1.practice;

public class MyMaxGap { //找出數(shù)組中相鄰兩個數(shù)的最大差值,要求時間復雜度為(N)
    public static int maxGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        int len=nums.length;
        for(int i=0;i<len;i++){ //找出最大值最小值
            if (nums[i]>max)
                 max=nums[i];
            if (nums[i]<min)
                min=nums[i];
        }
        //分三個桶隊列
        boolean[] hasNum = new boolean[len + 1]; //存放每個桶是否為空的判斷
        int[] maxs = new int[len + 1];//存放每個桶里的最大值
        int[] mins = new int[len + 1];//存放每個桶里的最小值
        int bid;//判斷i上的值在桶中的位置
        for(int i=0;i<len;i++){//遍歷數(shù)組.將數(shù)組中每個數(shù)組與對應(yīng)桶中位置上的數(shù)據(jù)比對,更新桶中最大值或最小值
            bid = bucket(nums[i], len, min, max);
            maxs[bid]=hasNum[bid]?Math.max(maxs[bid],nums[i]):nums[i];
            mins[bid]=hasNum[bid]?Math.max(maxs[bid],nums[i]):nums[i];
            hasNum[bid]=true;
        }
        int res = Integer.MIN_VALUE;
        int lastMax = maxs[0];
        int i = 1;
        for(;i<len+1;i++){
            if (hasNum[i]){//如果桶里有數(shù)據(jù),就用當前桶最小值和前一個桶最大值相減,結(jié)果再和res相比
                res=Math.max(mins[i]-lastMax,res);
                lastMax=maxs[i];
            }
        }
        return res;
    }
    public static int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }
    //test
    public static void main(String[] args){  
        int[] arrs=new int[]{2,5,8,9,4,22,44,23,21};
        int res=maxGap(arrs);
        System.out.println(res);
    }

}