Question

164. Maximum Gap

中文文档

Description

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.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Solutions

Solution 1

class Solution:
  def maximumGap(self, nums: List[int]) -> int:
    n = len(nums)
    if n < 2:
      return 0
    mi, mx = min(nums), max(nums)
    bucket_size = max(1, (mx - mi) // (n - 1))
    bucket_count = (mx - mi) // bucket_size + 1
    buckets = [[inf, -inf] for _ in range(bucket_count)]
    for v in nums:
      i = (v - mi) // bucket_size
      buckets[i][0] = min(buckets[i][0], v)
      buckets[i][1] = max(buckets[i][1], v)
    ans = 0
    prev = inf
    for curmin, curmax in buckets:
      if curmin > curmax:
        continue
      ans = max(ans, curmin - prev)
      prev = curmax
    return ans

class Solution {
  public int maximumGap(int[] nums) {
    int n = nums.length;
    if (n < 2) {
      return 0;
    }
    int inf = 0x3f3f3f3f;
    int mi = inf, mx = -inf;
    for (int v : nums) {
      mi = Math.min(mi, v);
      mx = Math.max(mx, v);
    }
    int bucketSize = Math.max(1, (mx - mi) / (n - 1));
    int bucketCount = (mx - mi) / bucketSize + 1;
    int[][] buckets = new int[bucketCount][2];
    for (var bucket : buckets) {
      bucket[0] = inf;
      bucket[1] = -inf;
    }
    for (int v : nums) {
      int i = (v - mi) / bucketSize;
      buckets[i][0] = Math.min(buckets[i][0], v);
      buckets[i][1] = Math.max(buckets[i][1], v);
    }
    int prev = inf;
    int ans = 0;
    for (var bucket : buckets) {
      if (bucket[0] > bucket[1]) {
        continue;
      }
      ans = Math.max(ans, bucket[0] - prev);
      prev = bucket[1];
    }
    return ans;
  }
}

using pii = pair<int, int>;

class Solution {
public:
  const int inf = 0x3f3f3f3f;
  int maximumGap(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return 0;
    int mi = inf, mx = -inf;
    for (int v : nums) {
      mi = min(mi, v);
      mx = max(mx, v);
    }
    int bucketSize = max(1, (mx - mi) / (n - 1));
    int bucketCount = (mx - mi) / bucketSize + 1;
    vector<pii> buckets(bucketCount, {inf, -inf});
    for (int v : nums) {
      int i = (v - mi) / bucketSize;
      buckets[i].first = min(buckets[i].first, v);
      buckets[i].second = max(buckets[i].second, v);
    }
    int ans = 0;
    int prev = inf;
    for (auto [curmin, curmax] : buckets) {
      if (curmin > curmax) continue;
      ans = max(ans, curmin - prev);
      prev = curmax;
    }
    return ans;
  }
};

func maximumGap(nums []int) int {
  n := len(nums)
  if n < 2 {
    return 0
  }
  inf := 0x3f3f3f3f
  mi, mx := inf, -inf
  for _, v := range nums {
    mi = min(mi, v)
    mx = max(mx, v)
  }
  bucketSize := max(1, (mx-mi)/(n-1))
  bucketCount := (mx-mi)/bucketSize + 1
  buckets := make([][]int, bucketCount)
  for i := range buckets {
    buckets[i] = []int{inf, -inf}
  }
  for _, v := range nums {
    i := (v - mi) / bucketSize
    buckets[i][0] = min(buckets[i][0], v)
    buckets[i][1] = max(buckets[i][1], v)
  }
  ans := 0
  prev := inf
  for _, bucket := range buckets {
    if bucket[0] > bucket[1] {
      continue
    }
    ans = max(ans, bucket[0]-prev)
    prev = bucket[1]
  }
  return ans
}

using System;
using System.Linq;

public class Solution {
  public int MaximumGap(int[] nums) {
    if (nums.Length < 2) return 0;
    var max = nums.Max();
    var min = nums.Min();
    var bucketSize = Math.Max(1, (max - min) / (nums.Length - 1));
    var buckets = new Tuple<int, int>[(max - min) / bucketSize + 1];
    foreach (var num in nums)
    {
      var index = (num - min) / bucketSize;
      if (buckets[index] == null)
      {
        buckets[index] = Tuple.Create(num, num);
      }
      else
      {
        buckets[index] = Tuple.Create(Math.Min(buckets[index].Item1, num), Math.Max(buckets[index].Item2, num));
      }
    }

    var result = 0;
    Tuple<int, int> lastBucket = null;
    for (var i = 0; i < buckets.Length; ++i)
    {
      if (buckets[i] != null)
      {
        if (lastBucket != null)
        {
          result = Math.Max(result, buckets[i].Item1 - lastBucket.Item2);
        }
        lastBucket = buckets[i];
      }
    }
    return result;
  }
}