Задача: 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 {
    func minimumDeviation(_ nums: [Int]) -> Int {
        var evens = PriorityQueue<Int>(ascending: false)
        var minimum = Int.max
        
        for num in nums {
            if num % 2 == 0 {
                evens.push(num)
                minimum = min(minimum, num)
            } else {
                evens.push(num * 2)
                minimum = min(minimum, num * 2)
            }
        }
        
        var minDeviation = Int.max
        
        while let currentValue = evens.pop() {
            minDeviation = min(minDeviation, currentValue - minimum)
            if currentValue % 2 == 0 {
                evens.push(currentValue / 2)
                minimum = min(minimum, currentValue / 2)
            } else {
                break
            }
        }
        
        return minDeviation
    }
}

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