↓Skip to main content
  1. Posts/

LeetCode-2542 最大子序列的分数

·1 min·
Table of Contents

LeetCode-2542 最大子序列的分数 #

Solution 1 #

考虑从大到小枚举子序列中最小的 $nums2$ 元素, 此时, 只有最大的 $k$ 个可选的 $nums1$ 元素的和变大才有可能使得分数变大, 用一个堆来维护 topK 的可选 $nums1$ 元素. 代码如下:

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        nums = sorted(zip(nums1, nums2), key=lambda p: -p[1])
        h = [x for x, _ in nums[:k]]
        heapify(h)
        s = sum(h)
        ans = s * nums[k - 1][1]
        for x, y in nums[k:]:
            if x > h[0]:
                s += x - heapreplace(h, x)
                ans = max(ans, s * y)
        return ans