164. Maximum Gap

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

Example 1:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Code

class Solution {
    public int maximumGap(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int len = nums.length;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for(int num : nums){
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // len - 1是有几个间隔
        int gap = (int)Math.ceil((double)(max - min) / (len - 1));

        int[] bucketsMin = new int[len - 1];
        int[] bucketsMax = new int[len - 1];

        Arrays.fill(bucketsMin, Integer.MAX_VALUE);
        Arrays.fill(bucketsMax, Integer.MIN_VALUE);

        for(int num : nums){
            if(num == max || num == min) continue;

            int bucket = (num - min) / gap;
            bucketsMin[bucket] = Math.min(bucketsMin[bucket], num);
            bucketsMax[bucket] = Math.max(bucketsMax[bucket], num);
        }

        int res = 0;
        int pre = min;

        for(int i = 0; i < len - 1; i++){
            if(bucketsMin[i] == Integer.MAX_VALUE || bucketsMax[i] == Integer.MAX_VALUE) continue;

            res = Math.max(res, bucketsMin[i] - pre);
            pre = bucketsMax[i];
        }

        res = Math.max(res, max - pre);
        return res;
    }
}