Posted on 2023-06-27 00:23
Uriel 阅读(45)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 、
闲来无事重切Leet Code
给定一个数列costs，一共k次操作，每次从前candidates和后candidates个数里面选较小的一个，问k次取到的k个数只和
维护两个优先队列，一个存前candidates，一个存后candidates，注意每次pop之后要push后一个/前一个数
1 #2462
2 #Runtime: 1356 ms (Beats 44.93%)
3 #Memory: 21.8 MB (Beats 68.12%)
4
5 class Solution(object):
6 def totalCost(self, costs, k, candidates):
7 """
8 :type costs: List[int]
9 :type k: int
10 :type candidates: int
11 :rtype: int
12 """
13 left = costs[:candidates]
14 right = costs[max(candidates, len(costs) - candidates):]
15 heapify(left)
16 heapify(right)
17 ans = 0
18 i = candidates
19 j = len(costs) - candidates - 1
20 for _ in range(k):
21 if (not right) or (left and left[0] <= right[0]):
22 ans += heappop(left)
23 if i <= j:
24 heappush(left, costs[i])
25 i += 1
26 else:
27 ans += heappop(right)
28 if i <= j:
29 heappush(right, costs[j])
30 j -= 1
31 return ans