Maximum Subsequence Score

2542. 最大子序列的分数

分析

贪心策略：
- 优先选择 nums2 值较大的元素，以确保当前子序列的最小值较大，即 min(nums2) 尽可能大，进而最大化分数
降序排序：
- 将 nums2 和 nums1 的对应元素组合成一个二元组 nums2[i], nums1[i]，并按 nums2 降序排列，这样我们可以从最大值开始依次考虑子序列
优先队列维护和：
- 使用一个最小堆 min_heap 来动态维护当前选定子序列中 nums1 的 k 个元素的和
- 如果堆的大小超过 k，移除堆顶（即当前最小的元素），从而保持堆的大小不超过 k
- 这样可以保证始终以较大的元素尽量填满子序列
更新最大分数：
- 每当堆的大小达到 k ，更新最大分数

时间复杂度

排序操作：O(n \log n)，其中 n 是数组的长度
遍历 combine 并维护堆：O(nlogk)，每次插入或删除堆顶操作需要 O(logk)

总时间复杂度：O(nlogn + nlogk)

空间复杂度

使用了一个最小堆，大小为 O(k)
存储组合后的数组，空间为 O(n)

总空间复杂度：O(n + k)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution
{
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k)
    {
        using PII = std::pair<int, int>;
        std::vector<PII> combine;

        // 将 nums1 和 nums2 的元素组合成二元组
        for (int i = 0; i < nums1.size(); ++i)
            combine.push_back({nums2[i], nums1[i]});

        // 按 nums2 降序排列
        std::sort(combine.rbegin(), combine.rend());

        long long nums1_sum = 0, max_score = 0;
        std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

        // 遍历每个元素，维护一个大小为 k 的子序列
        for (auto t : combine)
        {
            int num2 = t.first, num1 = t.second;
            nums1_sum += num1;
            min_heap.push(num1);

            // 如果堆大小超过 k，则移除最小值
            if (min_heap.size() > k)
            {
                nums1_sum -= min_heap.top();
                min_heap.pop();
            }

            // 更新最大分数
            if (min_heap.size() == k)
                max_score = std::max(max_score, nums1_sum * num2);
        }

        return max_score;
    }
};