Posted on 2023-05-24 21:32
Uriel 閱讀(67)
評論(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