164. Maximum Gap

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums == null ||
            nums.Length < 2) 
            return 0;
        Array.Sort(nums);
        int maxGap = 0;
        for (int i = 0; i < nums.Length - 1; i++)
            maxGap = Math.Max(nums[i + 1] - nums[i], maxGap);
        return maxGap;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaximumGap(vector<int>& nums) {
        if (nums == null ||
            nums.size() < 2) 
            return 0;
        sort(nums.begin(), nums.end());
        int maxGap = 0;
        for (int i = 0; i < nums.size() - 1; i++)
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        return maxGap;
    }
}

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

        int maxGap = 0;

        for (int i = 0; i < nums.length - 1; i++) maxGap = Math.max(
            nums[i + 1] - nums[i],
            maxGap
        );

        return maxGap;
    }
}

var maximumGap = function (nums) {
    if (nums == null || nums.length < 2)
        return 0;

    nums.sort((a, b) => a - b)

    var maxGap = 0;

    for (var i = 0; i < nums.length - 1; i++)
        maxGap = Math.max(nums[i + 1] - nums[i], maxGap);

    return maxGap;
};

class Solution:
    def maximumGap(self, nums):
        if (
            nums is None or len(nums) < 2
        ): 
            return 0

        nums.sort()  
        maxGap = 0

        for i in range(len(nums) - 1):
            maxGap = max(nums[i + 1] - nums[i], maxGap)

        return maxGap

func maximumGap(nums []int) int {
    if len(nums) < 2 { 
        return 0
    }

    sort.Ints(nums)
    maxGap := 0

    for i := 0; i < len(nums)-1; i++ {
        diff := nums[i+1] - nums[i]
        if diff > maxGap {
            maxGap = diff
        }
    }

    return maxGap
}

Algorithm

Ví dụ:

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.

👨‍💻

Thuật toán:

1️⃣

Инициализация:

Определите минимальное и максимальное значения в mảngе для расчета возможного максимального интервала (разрыва) между elementами в идеально распределенном mảngе.

Вычислите размер ведра (bucket size), необходимый для размещения всех elementов mảngа так, чтобы если mảng был равномерно распределен, каждый ведер должен содержать хотя бы один element. Размер ведра = (max_value - min_value) / (количество elementов - 1).

2️⃣

Размещение elementов в ведрах:

Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого elementа в соответствующем ведре на основе его значения.

Игнорируйте пустые ведра при расчете максимального интервала.

3️⃣

Вычисление максимального интервала:

Пройдите через ведра и вычислите maximum интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра.

maximum интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер.

😎