- Leetcode 3478. Choose K Elements With Maximum Sum
- 1. 解题思路
- 2. 代码实现
- 题目链接：3478. Choose K Elements With Maximum Sum
1. 解题思路
这一题思路上就是一个有序数组，我们首先将数组1有序排列，然后依次考察其每一个位置上的元素，此时就可以保证每一个位置上的元素被考察时，此前数组2当中对应位置的元素都是可用的，我们只需要取出topk个元素进行求和就行了。
当然，由于只需要考虑topk，因此事实上我们只需要维护最大的topk个元素及其对应的和的值即可。
2. 代码实现
给出python代码实现如下：
class Solution:def findMaxSum(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:n = len(nums1)ans = [0 for _ in range(n)]ordered_nums1 = sorted([(x, i) for i, x in enumerate(nums1)])pre_max, topk_sum = 0, 0cache, topk_elems = [], []for num, idx in ordered_nums1:if num > pre_max:for candidate in cache:if len(topk_elems) < k:bisect.insort(topk_elems, candidate)topk_sum += candidateelif topk_elems[0] < candidate:bisect.insort(topk_elems, candidate)topk_sum += candidate - topk_elems[0]topk_elems.pop(0)cache = []pre_max = numans[idx] = topk_sumcache.append(nums2[idx])return ans
提交代码评测得到：耗时1165ms，占用内存48.3MB。
