[LeetCode] 2542. Maximum Subsequence Score

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 i0, i1, ..., ik - 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[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 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 <= 105
• 0 <= nums1[i], nums2[j] <= 105
• 1 <= k <= n

最大子序列的分数。

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。

对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下：

nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。
用公示表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。
请你返回 最大 可能的分数。

一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subsequence-score
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心，具体做法需要用到排序和最小堆。

求分数的公式不难理解，参考例子一，每个子序列的分数 = nums1 中子序列的和 * nums2 中对应子序列的最小值。注意这里涉及到最小值，所以可能需要考虑对 nums2 降序排列，这样，排序后对于任何一个 nums2[i] ，他就可以被当做以 nums2[i] 结尾的子序列的最小值，同时找子序列的范围也就只会在 index = i 的左侧。这里我们不能单单只排序 nums2，所以我们把 nums1 和 nums2 中的元素变成一个二维数组然后对这个二维数组排序。

排序之后我们遍历每个 pair，当元素个数 = K 的时候，我们计算以 pair[1]（这是 nums2[i]）为结尾的子序列的分数，最后用一个变量 res 记录全局最大的分数。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public long maxScore(int[] nums1, int[] nums2, int k) {
 3         int n = nums1.length;
 4         int[][] pairs = new int[n][2];
 5         for (int i = 0; i < n; i++) {
 6             int[] pair = pairs[i];
 7             pair[0] = nums1[i];
 8             pair[1] = nums2[i];
 9         }
10         
11         // pairs按nums2从大到小排序
12         Arrays.sort(pairs, (a, b) -> b[1] - a[1]);
13         // 最小堆，存来自nums1的元素
14         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
15         long res = 0L;
16         long sum = 0L;
17         for (int[] pair : pairs) {
18             sum += pair[0];
19             minHeap.offer(pair[0]);
20             if (minHeap.size() > k) {
21                 sum -= minHeap.poll();
22             }
23             if (minHeap.size() == k) {
24                 res = Math.max(res, sum * pair[1]);
25             }
26         }
27         return res;
28     }
29 }

LeetCode 题目总结