Задача: 1675. Minimize Deviation in Array
Сложность: hard

Вам дан массив nums из n положительных целых чисел.
Вы можете выполнять два типа операций над любым элементом массива любое количество раз:
Если элемент четный, разделите его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на последнем элементе, и массив станет [1,2,3,2].
Если элемент нечетный, умножьте его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на первом элементе, и массив станет [2,2,3,4].
Отклонение массива — это максимальная разница между любыми двумя элементами в массиве.
Верните минимальное отклонение, которое может иметь массив после выполнения некоторого числа операций.

Пример:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

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

1⃣Инициализируйте max-heap под названием evens. Если элемент массива четный, добавьте его в evens; если элемент нечетный, умножьте его на 2 и добавьте в evens. Одновременно отслеживайте минимальный элемент в evens.

2⃣Извлекайте максимальный элемент из evens, обновляйте минимальное отклонение, используя максимальный элемент и текущий минимальный элемент. Если максимальный элемент четный, делите его на 2 и снова добавляйте в evens.

3⃣Повторяйте шаг 2 до тех пор, пока максимальный элемент в evens не станет нечетным. Верните минимальное отклонение.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function minimumDeviation($nums) {
        $evens = new SplPriorityQueue();
        $minimum = PHP_INT_MAX;
        
        foreach ($nums as $num) {
            if ($num % 2 == 0) {
                $evens->insert($num, $num);
                $minimum = min($minimum, $num);
            } else {
                $evens->insert($num * 2, $num * 2);
                $minimum = min($minimum, $num * 2);
            }
        }
        
        $minDeviation = PHP_INT_MAX;
        
        while (!$evens->isEmpty()) {
            $currentValue = $evens->extract();
            $minDeviation = min($minDeviation, $currentValue - $minimum);
            if ($currentValue % 2 == 0) {
                $evens->insert($currentValue / 2, $currentValue / 2);
                $minimum = min($minimum, $currentValue / 2);
            } else {
                break;
            }
        }
        
        return $minDeviation;
    }
}

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