最大子序列的分数

难度:

标签:

题目描述

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i₀, i₁, ..., i_{k - 1}, your score is defined as:

The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
It can defined simply as: (nums1[i₀] + nums1[i₁] +...+ nums1[i_{k - 1}]) * min(nums2[i₀] , nums2[i₁], ... ,nums2[i_{k - 1}]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.

Example 1:

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation: 
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

Example 2:

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation: 
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Constraints:

n == nums1.length == nums2.length
1 <= n <= 10⁵
0 <= nums1[i], nums2[j] <= 10⁵
1 <= k <= n

代码结果

运行时间: 137 ms, 内存: 34.4 MB

/* 
 思路：
 1. 使用Stream来处理数组操作。 
 2. 通过Stream找到所有可能的子序列分数，最后返回最大值。 
 */
import java.util.stream.IntStream;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class SolutionStream {
    public int maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        return IntStream.range(0, n)
                .boxed()
                .sorted((a, b) -> nums2[b] - nums2[a])
                .limit(k)
                .collect(Collectors.toList())
                .stream()
                .mapToInt(i -> nums1[i])
                .sum() * IntStream.range(0, n).map(i -> nums2[i]).min().orElse(0);
    }
}

解释

方法:

题解的核心思路基于排序和贪心算法。首先，将数组 nums1 和 nums2 基于 nums2 的值进行排序。排序之后，对于每一个可能的最小值（即 nums2 中的元素），选择在这个最小值之后的 K 个 nums1 元素的最大可能和。这是通过使用一个最小堆（优先队列）来维护当前的最大 K 个元素来实现的。随着从后向前遍历排序后的数组，我们更新当前的和并检查是否可以通过替换堆中最小的元素来获得更大的值。这样可以保证每一步都使用了当前最小值之后的 K 个最大值来计算分数。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在题解中选择将数组nums1和nums2基于nums2的值进行排序？这种排序的依据是什么？

▷

在题解中，数组nums1和nums2根据nums2的值进行排序的原因是：我们需要找到使得公式`(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0], nums2[i1], ..., nums2[ik - 1])`的值最大化的子序列。因此，我们关注的是nums2数组中的最小值，因为它会与nums1子序列的和相乘。通过对nums2进行排序，我们可以更容易地控制和操作nums2的最小值。对于任意选择的最小值min(nums2)，我们希望nums1中相应位置的元素和尽可能大，因此这种排序方式可以有效地将问题转化为一个更易于解决的形式。

🦆

在使用最小堆维护K个最大元素时，如何确保堆中始终保持的是K个最大值而不是任意K个值？

▷

在题解中使用最小堆来确保我们始终能够维护K个最大元素的原因是，最小堆允许我们快速访问堆中的最小值。每当新的元素加入到堆中，如果堆的大小超过K，我们就将堆顶（即堆中的最小值）移除。这样，堆中始终保留的是当前遇到的最大的K个元素。通过这种方式，我们实际上是在利用最小堆的性质来确保堆中保存的是最大的K个值，而非随机选择的K个数。

🦆

题解中提到，从后向前遍历数组并更新当前和，这种从后向前的遍历方式有什么特殊的优势吗？

▷

题解中从后向前遍历数组的主要优势是方便地处理与最小值相关的逻辑。由于数组已经根据nums2进行排序，从后向前遍历可以保证我们每次处理的都是当前最小值之后的元素。这样可以简化逻辑，因为我们总是在减小的nums2值中选择最小值，这保证了每次计算的分数都是基于当前遍历到的位置确定的最小值。此外，这种方法还有助于我们在更新最大和时，更容易地通过比较新加入的元素和堆中的最小元素来优化总和。

最大子序列的分数

题目描述

代码结果

解释

代码细节讲解

相关问题