Posted on 2023-02-25 20:31
Uriel 閱讀(71)
評論(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)