Posted on 2023-02-25 20:31
Uriel 阅读(27)
评论(0) 编辑 收藏 引用 所属分类:
贪心 、
闲来无事重切Leet Code
给出一列数，对于奇数，可以*2，对于偶数，可以/2，问执行任意多次操作之后，这列数的最大最小值之差最小是多少
参考了：https://leetcode.com/problems/minimize-deviation-in-array/solutions/3223578/priority-queue-video-java-c-python/
利用python的heapq
1 #1675
2 #Runtime: 5340 ms (Beats 100%)
3 #Memory: 19.7 MB (Beats 100%)
4 (Sorry, there are not enough accepted submissions to show data)
5
6 class Solution(object):
7 def minimumDeviation(self, nums):
8 """
9 :type nums: List[int]
10 :rtype: int
11 """
12 q = []
13 q_min = 2000000000
14 for i in nums:
15 if i % 2:
16 i *= 2
17 heapq.heappush(q, -i)
18 q_min = min(q_min, i)
19
20 ans = -q[0] - q_min
21 while q[0] % 2 == 0:
22 t = -heapq.heappop(q)
23 heapq.heappush(q, -(t // 2))
24 ans = min(ans, t - q_min)
25 q_min = min(q_min, t // 2)
26 return min(ans, -q[0] - q_min)