先将所有奇数变为偶数(尽可能大),然后将最大值从堆中取出来和堆中最小值做差,并将最大值$\frac{maxi}{2}$加入优先队列,用优先队列动态维护最大值,所有可能的最大值最小值集合就包含在动态更新的过程中
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
import heapq
n = len(nums)
mini = float('inf')
res = float('inf')
h = []
for i in range(n):
if nums[i]%2==1:
nums[i]*=2
heapq.heappush(h,-nums[i])
mini = min(mini,nums[i])
while True:
maxi = -heapq.heappop(h)
res = min(res,maxi-mini)
# print(maxi,res)
if maxi%2==1:
break
mini = min(mini,maxi//2)
heapq.heappush(h,-maxi//2)
return res