LeetCode_贪心算法_中等_2542.最大子序列的分数

绝地灬酷狼 2023-10-13 13:33 65阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你两个下标从 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\} 中删除若干元素得到的剩余集合，也可以不删除任何元素。

**示例 1：**  
输入：nums1 = \[1,3,3,2\], nums2 = \[2,1,3,4\], k = 3  
输出：12  
解释：  
四个可能的子序列分数为：

*  选择下标 0 ，1 和 2 ，得到分数 (1+3+3) \* min(2,1,3) = 7 。
 *  选择下标 0 ，1 和 3 ，得到分数 (1+3+2) \* min(2,1,4) = 6 。
 *  选择下标 0 ，2 和 3 ，得到分数 (1+3+2) \* min(2,3,4) = 12 。
 *  选择下标 1 ，2 和 3 ，得到分数 (3+3+2) \* min(1,3,4) = 8 。  
    所以最大分数为 12 。

**示例 2：**  
输入：nums1 = \[4,2,3,1,1\], nums2 = \[7,5,10,9,6\], k = 1  
输出：30  
解释：  
选择下标 2 最优：nums1\[2\] \* nums2\[2\] = 3 \* 10 = 30 是最大可能分数。

**提示：**  
n == nums1.length == nums2.length  
1 <= n <= 105  
0 <= nums1\[i\], nums2\[j\] <= 105  
1 <= k <= n

## 2.思路 ##

（1）贪心算法  
思路参考[该 LeetCode 用户题解][LeetCode]。

## 3.代码实现（Java） ##

//思路1————贪心算法
    class Solution {
        
        public long maxScore(int[] nums1, int[] nums2, int k) {
        
            int n = nums1.length;
            long res = 0L;
            Integer[] sorts = new Integer[n];
            for (int i = 0; i < n; i++) {
        
                sorts[i] = i;
            }
            //将 nums2 进行降序排序，排序后的下标结果映射到 sorts 中
            Arrays.sort(sorts, (a, b) -> nums2[b] - nums2[a]);
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            // sum 保存 nums1 中长度为 k 的子序列和
            long sum = 0L;
            for (int i = 0; i < k - 1; i++) {
        
                sum += nums1[sorts[i]];
                queue.offer(nums1[sorts[i]]);
            }
            for (int i = k - 1; i < n; i++) {
        
                sum += nums1[sorts[i]];
                queue.offer(nums1[sorts[i]]);
                //更新 res
                res = Math.max(res, nums2[sorts[i]] * sum);
                sum -= queue.poll();
            }
            return res;
        }
    }

[LeetCode]: https://leetcode.cn/problems/maximum-subsequence-score/solutions/2103910/yu-niang-niang-2542-zui-da-zi-xu-lie-de-vdxv6/