Beat 99.81% java coder


  • 20
    Q
    public class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if(n < 2) return 0;
        int min = nums[0];
        int max = nums[0];
        for(int i = 1;i < n;i++){
            if(min > nums[i]) min = nums[i];
            if(max < nums[i]) max = nums[i];
        }
        
        int gap = (max-min)/(n-1);
        if(gap == 0) gap++;
        int len = (max-min)/gap+1;
        int [] tmax = new int [len];
        int [] tmin = new int [len];
        
        for(int i = 0;i < n;i++){
            int index = (nums[i]-min)/gap;
            if(nums[i] > tmax[index]) tmax[index] = nums[i];
            if(tmin[index] == 0 || nums[i] < tmin[index]) tmin[index] = nums[i];
        }
        int myMax = 0;
        for(int i = 0;i < len;i++){
            if(myMax < tmin[i]-min) myMax = tmin[i]-min;
            if(tmax[i] != 0) min = tmax[i];
        }
        return myMax;
    }
    

    }


  • 1
    S

    @qinzhaokun If you had given a little explanation, may be you could have got more upvotes. Good code though!


  • 0
    A

    That's a good idea! by computing the average gap , and divide the numbers into several intervals . The maximumGap is between the intervals.


  • 0
    P

    @qinzhaokun Could you explain this? It will be of great help!!! Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.