贪心与优先队列相结合：如何高效求解最大子序列分数

在这篇文章中，我们将详细讲解如何从两个长度相同的数组 nums1 和 nums2 中选择 k 个元素的子序列，从而找到最大子序列分数。这道题目要求我们从 nums1 和 nums2 中分别选择相同索引的 k 个元素，然后计算 nums1 中选定元素的和，并乘以它们在 nums2 中的最小值。最后返回所有可能子序列组合中的最大分数。

题目链接：LeetCode 2542 - 最大子序列的分数

---

问题分析

1. 题目理解与示例

给定两个相同长度的数组 nums1 和 nums2，目标是选择 k 个元素的子序列，计算这些元素在 nums1 中的和，并乘以它们在 nums2 中的最小值，最后找到所有可能组合中分数的最大值。

举例说明：

• 示例 1：

  输入: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
  输出: 24
  解释: 选择子序列为 [3,3,2]，对应 nums2 的最小值为 2，则分数为 (3+3+2)*2 = 24。
  

• 示例 2：

  输入: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
  输出: 30
  解释: 选择 nums1 中的任意一个元素，乘以其对应 nums2 中的值即可得到最大分数。
  

2. 思路分析

为了更好地理解问题，我们需要考虑几个方面：

1. 如何选择子序列？

   • 从 nums1 中选择 k 个元素，并对应在 nums2 中选择同样索引的元素。

2. 如何最大化分数？

   • 分数计算为 nums1 选择 元素的和 sum 乘以 nums2 中选定元素的 最小值 min(nums2_selected)。
   • 因此，我们希望尽量选择 nums1 中较大的 k 个数，同时选择 nums2 中最小值较大的组合。

3. 复杂度与优化方向

   • 由于组合数量巨大，使用暴力枚举的方式会超时。我们需要一种高效的策略来筛选组合，从而减少计算量。

3. 常见错误与优化方向

如果使用暴力枚举所有可能的子序列组合，那么复杂度为 $O((\genfrac{}{}{0ex}{}{n}{k}))=\frac{n!}{k!(n-k)!}$，这是指数级别的复杂度，显然不适用于较大的 n 和 k。

因此，我们需要考虑使用贪心算法和优先队列（堆）来优化解决方案。

---

优化解法：贪心 + 优先队列

1. 思路阐述

通过观察题目，我们可以发现以下贪心策略：

• 我们希望 nums2 中的最小值尽可能大，因为它作为分数计算的乘数，影响最大。
• 因此，我们可以优先选择 nums2 中较大的元素进行组合，然后在这些组合中选择 nums1 中较大的元素。

为了实现这一策略：

1. 排序与配对：

   • 首先，我们将 nums1 和 nums2 配对，形成 (nums2[i], nums1[i]) 的对组，然后按照 nums2 的值从大到小进行排序。
   • 这样一来，我们在遍历时，可以保证每次遍历到的 nums2 的值是当前所有未遍历元素中的最大值，从而尽可能增加分数中的乘数值。

2. 优先队列维护最大 k 个 nums1：

   • 使用一个优先队列（最小堆）来维护当前 nums1 中的前 k 大元素的和。
   • 当堆中元素数量超过 k 个时，移除堆顶元素（最小值），保证堆中始终包含 k 个最大的 nums1 元素。

3. 计算分数与更新结果：

   • 每次遍历到 k 个元素时，计算当前组合的分数，即 sum(nums1_selected) * min(nums2_selected)。
   • 更新当前的最大分数。

2. 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;class Solution {
public:long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {int n = nums1.size();// 1. 创建配对数组，并按 nums2 从大到小排序vector<pair<int, int>> pairs(n);for (int i = 0; i < n; ++i) {pairs[i] = {nums2[i], nums1[i]};}sort(pairs.rbegin(), pairs.rend()); // 按照 nums2 降序排列// 2. 使用最小堆来维护 nums1 中最大的 k 个数priority_queue<int, vector<int>, greater<int>> minHeap;long long sum = 0, result = 0;// 3. 遍历排序后的数组for (int i = 0; i < n; ++i) {int num1 = pairs[i].second;int num2 = pairs[i].first;// 将当前 num1 加入堆中minHeap.push(num1);sum += num1;// 如果堆中元素超过了 k 个，移除最小的那个if (minHeap.size() > k) {sum -= minHeap.top();minHeap.pop();}// 如果堆中的元素正好是 k 个，计算当前的分数if (minHeap.size() == k) {result = max(result, sum * num2); // 当前 sum * nums2 中的最小值}}return result;}
};

3. 代码详解

1. 排序操作：

   • 将 nums1 和 nums2 的元素进行配对，生成 (nums2[i], nums1[i]) 的形式，并按照 nums2 的值从大到小进行排序。
   • 排序的时间复杂度为 $O(n\log n)$。

2. 优先队列维护前 k 大元素：

   • 使用最小堆（优先队列）来维护当前选定的 k 个 nums1 元素的和。
   • 每次加入一个新的元素时，如果堆中元素超过 k，则移除堆顶最小元素，以保证堆中是当前最大的 k 个元素。

3. 分数计算与结果更新：

   • 当堆中元素达到 k 个时，计算当前组合的分数。
   • 分数等于堆中 nums1 元素的和 sum，乘以当前 nums2 中的最小值（因为是按降序排列，所以 nums2 中的最小值就是当前遍历的元素）。

4. 时间复杂度分析

• 排序： $O(n\log n)$。
• 堆操作： 遍历每个元素并对堆进行插入或删除操作，每次操作的时间复杂度为 $O(\log k)$，因此总的时间复杂度为 $O(n\log k)$。

总时间复杂度为 $O(n\log n)$，相对于暴力枚举的指数级复杂度，这种方式显著提升了算法的效率。

---

示例讲解

示例 1：

输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3

1. 首先，我们对 nums2 从大到小进行排序：

   • 排序后的配对数组为 [(4, 2), (3, 3), (2, 1), (1, 3)]。

2. 使用最小堆维护 k = 3 个最大的 nums1 元素：

   • 第一个配对 (4, 2)：加入堆，当前堆为 [2]，和为 2，当前最小 nums2 为 4，暂时不计算。
   • 第二个配对 (3, 3)：加入堆，当前堆为 [2, 3]，和为 5，当前最小 nums2 为 3，暂时不计算。
   • 第三个配对 (3, 3)：加入堆，当前堆为 [2, 3, 3]，和为 8，此时堆中有 3 个元素，可以计算分数为 8 * 3 = 24。
   • 第四个配对 (2, 1)：堆已满，且此时堆顶最小元素为 2，替换后和不变，最终分数为 24。

输出：24。

示例 2：

输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1

1. 对 nums2 从大到小排序：

   • 排序后的配对数组为 [(10, 3), (9, 1), (7, 4), (6, 1), (5, 2)]。

2. 使用最小堆维护 k = 1 个最大的 nums1 元素：

   • 第一个配对 (10, 3)：堆中元素为 [3]，分数为 3 * 10 = 30。
   • 后续配对都不比此分数大，最终结果为 30。

输出：30。

总结

通过贪心策略和优先队列的结合，我们能够高效解决“最大子序列的分数”这一问题。核心思路在于排序 nums2 来优先选择最大乘数，然后通过维护 nums1 中最大和的 k 个数来最大化分数。希望这篇文章能够帮助你深入理解该题目的优化方法和代码实现。