LeetCode 2542. 最大子序列的分数

约 7 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 LeetCode 75
标签
数组 排序 贪心 堆（优先队列）

题目描述

✅ 2542. 最大子序列的分数

image-20260928234559655

image-20260928234559660

题意分析

在两个等长数组中选择同一组恰好 k 个不同下标，得分等于所选 nums1 元素之和，乘以所选 nums2 元素中的最小值，求最大可能得分。

下标可以不连续，但两个数组的配对不能拆开。元素均为非负数，这既影响固定最小值后怎样优化和，也支撑后面的阈值证明；必须恰好选择 k 项，不是最多选 k 项。

解法：按最小值阈值降序扫描并维护前k大和

核心思路

[!blue]

得分同时取决于一组元素的和与最小值，直接枚举下标组合代价太高。先按 nums2 从大到小处理原下标，将当前值 t 看作允许选择的最低阈值：此时已处理元素的 nums2 都不小于 t。

固定非负阈值 t 后，要让候选乘积最大，只需在已处理元素里保留最大的 k 个 nums1。用小顶堆保存这些值，sum 保存堆内之和；新值入堆后若超过 k 项，就弹出最小值并从 sum 扣除，堆始终留下当前和最大的 k 项。

堆满 k 项时计算 sum * t。注意当前下标可能刚被堆淘汰，所以 t 不一定就是堆内所选集合的真实最小 nums2，只能保证它不大于那个最小值。由于 sum 非负，计算出的候选不会超过这一合法集合的真实得分，因此不会把答案估得过高。

还需说明不会漏掉最优解。取任意一个全局最优集合，在它最后一个下标被处理的那一轮，它的全部 k 项都已进入候选范围，当前阈值恰好等于它的最小 nums2。堆保存的最大 k 项之和不小于该最优集合的和，因此这一轮候选至少达到全局最优得分。

所有候选都不超过全局最优值，又存在一轮能达到它，两边结合便证明取最大候选正确。这也解释了为何代码不必强制当前下标留在堆里，但不能把证明直接套到含负数的版本。

排序下标而非分别排序两数组，保持同一人的两项数值绑定。累计和和最终乘积均使用 64 位整数，答案从零开始也覆盖全零得分。

解题步骤

  1. 建立下标数组，按对应 nums2 值降序排序。
  2. 依次将当前 nums1 加入小顶堆，并加入 64 位累计和。
  3. 堆超过 k 个元素时弹出最小值，同步从累计和扣除。
  4. 堆恰有 k 项时，用累计和乘当前 nums2 阈值更新最大答案。
  5. 所有下标处理后返回最大得分。

代码实现

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        // 排序的是下标，因为两个数组靠下标绑定，必须整体搬动。
        Integer[] idx = new Integer[n];

        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }

        Arrays.sort(idx, (a, b) -> nums2[b] - nums2[a]);

        // 小顶堆：堆顶是当前选中的 nums1 值里最小的那个，也是最该被淘汰的。
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        long sum = 0;
        long answer = 0;

        for (int t = 0; t < n; t++) {
            int i = idx[t];

            heap.offer(nums1[i]);
            sum += nums1[i];

            if (heap.size() > k) {
                sum -= heap.poll();
            }

            if (heap.size() == k) {
                answer = Math.max(answer, sum * nums2[i]);
            }
        }

        return answer;
    }
}

import (
    "sort"
)

func maxScore(nums1 []int, nums2 []int, k int) int64 {
    n := len(nums1)
    // 排序的是下标，因为两个数组靠下标绑定，必须整体搬动。
    idx := make([]int, n)
    for i := range idx {
        idx[i] = i
    }
    sort.Slice(idx, func(a, b int) bool {
        return nums2[idx[a]] > nums2[idx[b]]
    })

    // 小顶堆：堆顶是当前选中的 nums1 值里最小的那个，也是最该被淘汰的。
    minHeap := make([]int, 0, k+1)

    push := func(x int) {
        minHeap = append(minHeap, x)
        i := len(minHeap) - 1
        for i > 0 {
            p := (i - 1) / 2
            if minHeap[p] <= minHeap[i] {
                break
            }
            minHeap[p], minHeap[i] = minHeap[i], minHeap[p]
            i = p
        }
    }

    pop := func() int {
        top := minHeap[0]
        last := len(minHeap) - 1
        minHeap[0] = minHeap[last]
        minHeap = minHeap[:last]
        i := 0
        for {
            l, r := i*2+1, i*2+2
            if l >= len(minHeap) {
                break
            }
            best := l
            if r < len(minHeap) && minHeap[r] < minHeap[l] {
                best = r
            }
            if minHeap[i] <= minHeap[best] {
                break
            }
            minHeap[i], minHeap[best] = minHeap[best], minHeap[i]
            i = best
        }
        return top
    }

    sum := int64(0)
    answer := int64(0)

    for _, i := range idx {
        push(nums1[i])
        sum += int64(nums1[i])
        if len(minHeap) > k {
            sum -= int64(pop())
        }
        if len(minHeap) == k {
            if cand := sum * int64(nums2[i]); cand > answer {
                answer = cand
            }
        }
    }

    return answer
}

复杂度分析

  • 时间复杂度：$O(n\log n + n\log(k + 1))$，排序下标加上每项的堆操作；由于 k <= n，总上界为 $O(n\log(n + 1))$。
  • 空间复杂度：$O(n)$，下标排序数组占线性空间，堆最多保存 k + 1 个值。

关键点总结

[!green]

  • 按瓶颈值降序枚举阈值，将同一轮的优化缩减为最大的 k 项和。
  • 当前阈值是堆内真实最小值的下界，不保证对应元素仍在堆里。
  • 正确性需要同时证明候选不会超过真实最优值，以及某轮能够达到最优值。
  • 非负和与非负阈值保证比较方向不反转，两个数组必须按下标绑定。

易错点总结

[!yellow]

  • 分别排序两数组会破坏原下标配对，得到题目不允许的组合。
  • 使用大顶堆淘汰最大 nums1 会留下较小的和，应从小顶堆弹出最小项。
  • 堆不足 k 项时不能更新答案，否则违反恰好选择的要求。
  • 不能把当前 nums2 始终解释成堆中真实最小值，当前项可能已经出堆。
  • 先在 32 位中求乘积再转换仍可能溢出，应让累计和与乘法从一开始使用 64 位。

相似题目

题目 难度 关联与区别
1383. 最大的团队表现值 困难 同样按瓶颈值降序扫描，用堆维护可加贡献；原题最多选k人，本题恰好选k项。
215. 数组中的第K个最大元素 中等 小顶堆维护前k大元素是核心子过程，本题同时累计这些元素的和，并结合另一数组阈值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/41971273
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！