Задача: 164. Maximum Gap
Сложность: medium

Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0.

Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство.

Пример:

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.

👨‍💻 Алгоритм:

1⃣Инициализация:
Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве.
Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1).

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

3⃣Вычисление максимального интервала:
Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра.
Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер.

😎 Решение:

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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний