2542. Maximum Subsequence Score

Leetcode link

题目简介

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */

题目给我们两个等长数字数组 nums1 与 nums2；以及一个数字 k

要求在两个数组中选择相同的 k 个下标，使得 nums1[0...k] 之和与 nums2[0...k] 中最小的数乘积最大

最后返回最大的乘积

解题思路

要让返回的值最大，有两个因素我们需要考虑：

1. 让 nums1[0...k] 之和 最大
2. 让 nums2[0...k] 中最小的数最大

其中第二点的因素影响更大，所以我们需要优先让第二点因素变大

为此我们需要针对 nums2 进行降序排序，排序过程中需要保留 nums1 与 nums2 数组下标元素的映射关系

加下来我们需要顺序遍历 nums2，但是遍历前还需要做一件事

我们需要用小顶堆 heap 来记录遍历过的 nums2 对应的 nums1，这样如果 heap 超过 k 个了，就可以直接 pop 最小的元素出去

最后，在遍历过程中如果 heap 长度等于 k，我们需要记录一下当前的乘积值

最后返回最大的乘积值即可

Javascript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
var maxScore = function (nums1, nums2, k) {
    let res = 0
    let sum = 0
    // create a new array with nums1[i] and nums2[i] and sorted by nums2
    const merged = nums1.map((item, idx) => [nums2[idx], item]).sort((a, b) => b[0] - a[0])
    // use min heap to pick the smallest nums1
    const heap = new PriorityQueue((a, b) => a - b)

    for (const [num2, num1] of merged) {
        if (heap.size() === k) {
            sum -= heap.pop()
        }

        heap.push(num1)
        sum += num1

        if(heap.size() === k) {
            res = Math.max(res, sum * num2)
        }
    }

    return res
};

复杂度分析

时间

排序：O(nlogn)

堆的 push 与 pop：O(logn)

遍历 nums2: O(n)

全部加起来是 O(nlogn)

空间

O(n) 主要来源于 merged 数组