当前位置：首页 > news >正文

LeetCode -- Maximum Gap

news 来源：原创 2024/5/6 1:10:08

题目描述：

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

本题直接使用.net内置（或其他编程语言）的排序算法就可以，然后计算间隔找出最大的就行了。

以下是一种最简单的实现方式，调用 LINQ的sort（内部实现为stable的快排）然后计算间隔。

public class Solution {
    public int MaximumGap(int[] nums) 
    {
        if(nums == null || nums.Length < 2){
    		return 0;
    	}
    	
    	var lst = nums.OrderBy(n=>n).ToList();
    	var max = 0;
    	for(var i = 0;i < lst.Count - 1; i++){
    		max = Math.Max(max, lst[i+1] - lst[i]);
    	}
    	
    	return max;
    }




}

官方的答案是使用桶排：
1. 求出最大最小值，一共需要nums.Length / (max - min)个桶
2. 遍历nums的过程中判断nums[i]属于哪个桶，然后将元素放入指定的桶中
3. 维护每个桶的最大最小值
4. 遍历桶的最值，它们之间的间隔(bucket[i-1]的最小值与bucket[i]的最大值)

以下实现参考了：
http://www.programcreek.com/2014/03/leetcode-maximum-gap-java/

public class Solution {
    public int MaximumGap(int[] nums) 
    {
        if(nums == null || nums.Length < 2){
    		return 0;
    	}
    	
    	// find the max and min
    	int max = nums[0];
        int min = nums[0];
        for(int i = 1; i < nums.Length; i++){
            max = Math.Max(max, nums[i]);
            min = Math.Min(min, nums[i]);
        }
     
        // init bucket
        var buckets = new Bucket[nums.Length + 1];
        for(int i=0; i < buckets.Length; i++){
            buckets[i] = new Bucket();
        }
     
        double height = (double) nums.Length / (max - min);// bucket height
        
        // loop each element in nums, find the bucket for it.
        for(int i=0; i<nums.Length; i++){
            int index = (int) ((nums[i] - min) * height);
     
            if(buckets[index].low == null){
                buckets[index].low = nums[i];
                buckets[index].high = nums[i];
            }else{
                buckets[index].low = Math.Min(buckets[index].low.Value, nums[i]);
                buckets[index].high = Math.Max(buckets[index].high.Value, nums[i]);
            }
        }


        int result = 0;
        int prev = buckets[0].high.Value;
        for(int i=1; i<buckets.Length; i++){
            if(buckets[i].low != null){
                result = Math.Max(result, buckets[i].low.Value-prev);
                prev = buckets[i].high.Value;
            }
     
        }
     
        return result;
    }


public class Bucket{
   public int? low;
   public int? high;
    public Bucket(){


    }
}


}