数组的最小偏移量

难度: Hard

给你一个由 n 个正整数组成的数组 nums 。

你可以对数组的任意元素执行任意次数的两类操作：

如果元素是偶数，除以 2
- 例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
如果元素是奇数，乘上 2
- 例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]

数组的 偏移量 是数组中任意两个元素之间的 最大差值 。

返回数组在执行某些操作之后可以拥有的 最小偏移量 。

示例 1：

输入：nums = [1,2,3,4]
输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1

示例 2：

输入：nums = [4,1,5,20,3]
输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3

示例 3：

输入：nums = [2,10,8]
输出：3

提示：

n == nums.length
2 <= n <= 5 * 10⁴
1 <= nums[i] <= 10⁹

Submission

运行时间: 181 ms

内存: 23.2 MB

class Solution:
    def minimumDeviation(self, nums):
        heap = []
        for num in nums:
            if num % 2 == 1:
                heapq.heappush(heap, -num * 2)
            else:
                heapq.heappush(heap, -num)
        mi = max(heap)
        res = abs(heap[0] - mi)
        while res > 0 and heap[0] % 2 == 0:
            max_num = heapq.heappop(heap)
            res = min(res,abs(max_num-mi))
            heapq.heappush(heap,max_num//2)
            mi = max(mi,max_num//2)
        res = min(res,mi - heap[0])
        return res

Explain

首先，为了确保每个数字都可以有效地进行操作（即奇数乘以2变偶数，偶数除以2直到成为奇数），我们将所有奇数都乘以2以统一初始状态。使用最大堆（实际上使用了负数实现最小堆的逆序）来存储这些转换后的数字，以便快速获取当前的最大值。堆的最大值（即负数绝对值最小）代表了当前数组的最大值。我们持续从堆中取出最大值，并尝试将其减半（即最大偶数除以2），然后将新值推回堆中，更新当前的最大值。通过这种方式，我们试图不断缩小数组元素之间的最大差异，即偏移量。每次操作后，都会更新当前的最小偏移量，直到堆顶元素为奇数为止（因为奇数不能再减半）。

时间复杂度: O(n log(n) log(maxNum))

空间复杂度: O(n)

class Solution:
    def minimumDeviation(self, nums):
        heap = []  # 使用堆来存储调整后的数组元素
        for num in nums:
            if num % 2 == 1:  # 如果是奇数，则乘2后加入堆
                heapq.heappush(heap, -num * 2)
            else:  # 如果是偶数，直接加入堆
                heapq.heappush(heap, -num)
        mi = max(heap)  # 初始化最小值为堆中的最大值
        res = abs(heap[0] - mi)  # 初始最大差异
        while res > 0 and heap[0] % 2 == 0:  # 只要堆顶是偶数就继续
            max_num = heapq.heappop(heap)  # 弹出最大值
            res = min(res, abs(max_num - mi))  # 更新最小偏移量
            heapq.heappush(heap, max_num // 2)  # 将最大值减半后放回堆中
            mi = max(mi, max_num // 2)  # 更新最小值
        res = min(res, mi - heap[0])  # 最终的最小偏移量
        return res

Explore

在开始时将所有奇数乘以2是为了简化操作和统一处理流程。由于奇数乘以2后变成偶数，这样一来，我们可以统一地对数组中的数进行除以2的操作，直至它们不再是偶数（即变为奇数）。这种做法的目的是使得所有的数字都能通过相同的操作（即连续除以2）达到其最小可能值，从而更方便地比较和计算最小偏移量。此外，这样也确保了在最大堆中每个数字都可以经过相同的处理流程，简化了问题的复杂度。

在Python中，标准库heapq实现的是最小堆，而不是最大堆。因此，为了通过heapq库来获取最大堆的效果，我们可以将所有元素的符号取反（即乘以-1），这样原本数值大的现在变为最小，便可以利用最小堆的性质来模拟最大堆的操作。这种方法免去了自己实现一个最大堆的复杂性，利用现有的库简化了代码实现。

使用负数来表示堆中的元素，实际上是借助了最小堆的性质来模拟最大堆。在这种情况下，最大值（原本的正数中的最大值）通过取负变成了最小值，因此在最小堆中位于顶部。这种表示方法的正确性保证在于数值转化的一致性（即所有数都取相反数），而效率则来源于Python的heapq库，该库为二叉堆提供了高效的实现，对于堆操作（如插入、删除顶部元素）均能在对数时间内完成。

每次从堆中取出最大值（即堆顶的负数绝对值最小的数），并将其减半后，再次加入堆中，这个操作实际上是更新了堆的结构。由于我们是将最大值减半，所以重新加入堆中的数要么还是当前的最大值，要么变得更小。这会导致堆的重新调整（heapify），保证了堆顶始终是当前最大值的负数。这种动态更新的过程是必要的，因为它保证了我们每次都能获取到当前数组中的最大值，并据此来尝试减少最大和最小值之间的差异，直到达到可能的最小偏移量。