Задача: 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 не станет нечетным. Верните минимальное отклонение.

😎 Решение:

import heapq

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        evens = []
        minimum = float('inf')
        
        for num in nums:
            if num % 2 == 0:
                heapq.heappush(evens, -num)
                minimum = min(minimum, num)
            else:
                heapq.heappush(evens, -num * 2)
                minimum = min(minimum, num * 2)
        
        minDeviation = float('inf')
        
        while evens:
            currentValue = -heapq.heappop(evens)
            minDeviation = min(minDeviation, currentValue - minimum)
            if currentValue % 2 == 0:
                heapq.heappush(evens, -currentValue // 2)
                minimum = min(minimum, currentValue // 2)
            else:
                break
        
        return minDeviation

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