title
给你一个由 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.length2 <= n <= 1051 <= nums[i] <= 109
solution
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
if not nums: return 0
n = len(nums)
right = [x for x in nums]
left = [x for x in nums]
for i, v in enumerate(nums):
# right v
right[i] = v
if v % 2 == 1:
right[i] = 2 * v
while v % 2 == 0:
v //= 2
# left v
left[i] = v
hq = []
import heapq
maxv = float('-inf')
ans = float('inf')
for i, x in enumerate(left):
heapq.heappush(hq, (x, i))
maxv = max(maxv, x)
ans = maxv - hq[0][0]
while True:
top, k = heapq.heappop(hq)
ans = min(ans, maxv - top)
if top == right[k]:
# minv不能再大了，这是第k个的最大值了。
return ans
heapq.heappush(hq, (top * 2, k))
maxv = max(maxv, top * 2)
return ans