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

在这篇文章中，我们将详细讲解如何从两个长度相同的数组 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. 思路分析

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

如何选择子序列？
- 从 nums1 中选择 k 个元素，并对应在 nums2 中选择同样索引的元素。
如何最大化分数？
- 分数计算为 nums1 选择元素的和 sum 乘以 nums2 中选定元素的最小值 min(nums2_selected)。
- 因此，我们希望尽量选择 nums1 中较大的 k 个数，同时选择 nums2 中最小值较大的组合。
复杂度与优化方向
- 由于组合数量巨大，使用暴力枚举的方式会超时。我们需要一种高效的策略来筛选组合，从而减少计算量。

3. 常见错误与优化方向

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

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

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

1. 思路阐述

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

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

为了实现这一策略：

排序与配对：
- 首先，我们将 nums1 和 nums2 配对，形成 (nums2[i], nums1[i]) 的对组，然后按照 nums2 的值从大到小进行排序。
- 这样一来，我们在遍历时，可以保证每次遍历到的 nums2 的值是当前所有未遍历元素中的最大值，从而尽可能增加分数中的乘数值。
优先队列维护最大 k 个 nums1：
- 使用一个优先队列（最小堆）来维护当前 nums1 中的前 k 大元素的和。
- 当堆中元素数量超过 k 个时，移除堆顶元素（最小值），保证堆中始终包含 k 个最大的 nums1 元素。
计算分数与更新结果：
- 每次遍历到 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. 代码详解

排序操作：
- 将 nums1 和 nums2 的元素进行配对，生成 (nums2[i], nums1[i]) 的形式，并按照 nums2 的值从大到小进行排序。
- 排序的时间复杂度为 $\log n)$ 。
优先队列维护前 k 大元素：
- 使用最小堆（优先队列）来维护当前选定的 k 个 nums1 元素的和。
- 每次加入一个新的元素时，如果堆中元素超过 k，则移除堆顶最小元素，以保证堆中是当前最大的 k 个元素。
分数计算与结果更新：
- 当堆中元素达到 k 个时，计算当前组合的分数。
- 分数等于堆中 nums1 元素的和 sum，乘以当前 nums2 中的最小值（因为是按降序排列，所以 nums2 中的最小值就是当前遍历的元素）。

4. 时间复杂度分析

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

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

示例讲解

示例 1：

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

首先，我们对 nums2 从大到小进行排序：
- 排序后的配对数组为 [(4, 2), (3, 3), (2, 1), (1, 3)]。
使用最小堆维护 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

对 nums2 从大到小排序：
- 排序后的配对数组为 [(10, 3), (9, 1), (7, 4), (6, 1), (5, 2)]。
使用最小堆维护 k = 1 个最大的 nums1 元素：
- 第一个配对 (10, 3)：堆中元素为 [3]，分数为 3 * 10 = 30。
- 后续配对都不比此分数大，最终结果为 30。