Posted on 2023-05-24 21:32
Uriel 阅读(39)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 、
闲来无事重切Leet Code
给出同样长度的两列数nums1，num2，求其中长度为k的子串，使得max(sum(a_i)*min(b_i))，a_i, b_i∈长度k的子串，输出max结果，优先队列基本应用
1 #2542
2 #Runtime: 1378 ms (Beats 42.86%)
3 #Memory: 42.3 MB (Beats 33.33%)
4
5 class Solution(object):
6 def maxScore(self, nums1, nums2, k):
7 """
8 :type nums1: List[int]
9 :type nums2: List[int]
10 :type k: int
11 :rtype: int
12 """
13 hp = []
14 ans, t_sum = 0, 0
15 for a, b in sorted(list(zip(nums1, nums2)), key=itemgetter(1), reverse=True):
16 t_sum += a
17 heappush(hp, a)
18 if len(hp) == k:
19 ans = max(ans, t_sum * b)
20 t_sum -= heappop(hp)
21 return ans