LeetCode 2542. 最大子序列的分数

2026-07-14 HGNULB 约 15 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 2542. 最大子序列的分数

题意分析

给两个等长数组 nums1 与 nums2，要从下标集合里挑出恰好 k 个位置。分数定义为「这 k 个位置在 nums1 上的取值之和」乘以「这 k 个位置在 nums2 上的取值的最小值」。求分数的最大值。

第一件要看清的事：题目虽然叫「子序列」，但下标的先后顺序完全不影响分数——求和与求最小值都是与顺序无关的运算。所以这道题实质上是「选一个大小为 k 的下标子集」，而不是真正意义上的子序列问题。这一点很重要，它意味着我们可以任意重排下标，不会破坏任何约束。

第二件事：两个数组通过同一个下标绑定在一起，选中一个位置就同时拿走它的 nums1 值和 nums2 值，不能拆开取。这是唯一的耦合来源。

第三件事：目标函数是两个因子的乘积，而这两个因子的性质完全不同。左边是可加的——多选一个位置就多加一份，越多越好；右边是取极值的，多选一个位置只可能让最小值变小或不变，越多越糟。两个因子朝相反方向拉扯，正是本题的核心张力。

数据规模上，两个数组长度可达 $10^5$，元素值可达 $10^5$。所以和最大约 $10^{10}$，再乘上最小值可达 $10^{15}$——必须用 64 位整型，返回值类型本身也是长整型。同时这个规模排除了任何 $O(n^2)$ 的做法。

边界包括：k 等于数组长度（只有一种选法）；k = 1（答案是所有位置各自乘积的最大值）；nums2 中存在大量相同值；以及所有 nums1 值都相同。

解法：按 nums2 降序枚举最小值 + 小顶堆维护 nums1 前 k 大

核心思路

暴力做法是枚举所有大小为 k 的下标子集，$\binom{n}{k}$ 量级，完全不可行。稍好一点的想法是「优先选 nums1 大的位置」，但立刻会被反例打脸——nums1 最大的那几个位置可能对应着极小的 nums2 值，把整体乘积拖垮。反过来「优先选 nums2 大的位置」同样不对，因为那些位置的 nums1 可能都很小。两个因子必须一起考虑。

瓶颈在于「最小值」这个因子是被整个选择集合共同决定的，无法在逐个挑选时局部判断。破局的办法是把它从未知量变成枚举量。

关键观察：设最终选中的 k 个位置里，nums2 最小的那个位置是 p。一旦固定了 p，右因子就锁死为 nums2[p]，而左因子的最优选法立刻变得显然——在所有满足 nums2[i] >= nums2[p] 的位置中，挑 nums1 最大的 k 个（其中必须包含 p 本身）。因为右因子已经固定，剩下的唯一目标就是把左边的和做到最大。

于是问题被拆成 n 个独立的子问题：对每个可能的 p，求「nums2 不小于 nums2[p] 的那些位置中，nums1 的前 k 大之和」，再乘以 nums2[p]，取所有结果的最大值。

直接对每个 p 重新扫一遍是 $O(n^2)$。让它变成线性对数的办法是按 nums2 从大到小遍历：这样当处理到位置 p 时，之前已经处理过的位置恰好就是「nums2 不小于 nums2[p]」的那些，它们构成一个只增不减的候选池。于是「前 k 大之和」可以增量维护——用一个小顶堆装当前选中的 k 个 nums1 值，堆顶是其中最小的那个；每来一个新值就压进去，若堆的大小超过 k 就弹掉堆顶（当前最小者），同时同步维护堆内元素之和。

不变量是：遍历到第 t 个位置时，堆中恰好是前 t 个位置（按 nums2 降序）里 nums1 最大的那 $\min(t, k)$ 个，sum 是它们的和。每压入一个新元素并弹出当前最小者，仍然保持「留下的是最大的 k 个」，不变量得以维持。

只有当堆的大小恰好等于 k 时才更新答案，此时 sum * nums2[i] 是一个合法且在「以 i 为最小值位置」这一约束下最优的分数。注意此刻 nums2[i] 一定是堆中所有位置里 nums2 的最小值——因为它们都在 i 之前或就是 i，而遍历是按 nums2 降序的。

遍历完成后，所有可能的最小值位置都被枚举过，答案就是其中的最大者。

解题步骤

构造下标数组并按 nums2 降序排序。排序的对象是下标而不是数值本身，因为两个数组靠下标绑定，必须整体搬动。降序是关键：它保证「已处理集合」始终等于「nums2 不小于当前值的集合」。

准备一个小顶堆和一个 64 位的和累加器。选小顶堆而非大顶堆，是因为要淘汰的永远是当前最小的 nums1 值——只有小顶堆能 $O(1)$ 拿到它。用错方向会把最大的那个扔掉，结果反而更差。

按排好的顺序逐个处理下标 i：把 nums1[i] 压入堆，同时把它加进 sum。压入必须无条件进行，因为要先让它参与竞争，再决定谁被淘汰。

若堆的大小超过 k，弹出堆顶并从 sum 中减去它。这一步把候选池重新压回 k 个。弹出与减法必须成对出现，任何一边漏掉都会让 sum 与堆内容脱节。

若堆的大小恰好等于 k，用 sum * nums2[i] 更新答案。判定用「等于」而不是「不小于」也可以（大小永远不会超过 k），但更重要的是它必须写在弹出之后——弹出之前堆里可能有 k + 1 个元素，sum 不是合法的前 k 大之和。

乘法两侧都要转成 64 位再相乘。sum 本身已是 64 位，nums2[i] 是 32 位，在多数语言里会自动提升；但若把 sum 写成 32 位，乘积会在 $10^{15}$ 量级上悄无声息地溢出。

返回累计的最大值。初始值取 0 是安全的，因为所有元素都是正整数，分数不可能为负。

以 nums1 = [1, 3, 3, 2]、nums2 = [2, 1, 3, 4]、k = 3 走一遍，预期答案 12。

按 nums2 降序排下标：nums2[3] = 4、nums2[2] = 3、nums2[0] = 2、nums2[1] = 1，所以顺序是下标 3、2、0、1。

处理下标 3：压入 nums1[3] = 2，sum = 2，堆是 {2}，大小 1 小于 3，不更新答案。

处理下标 2：压入 nums1[2] = 3，sum = 5，堆是 {2, 3}，大小 2，仍不更新。

处理下标 0：压入 nums1[0] = 1，sum = 6，堆是 {1, 2, 3}，大小恰好 3。此时 nums2[0] = 2 就是这三个位置里 nums2 的最小值，分数为 $6 \times 2 = 12$，答案更新为 12。

处理下标 1：压入 nums1[1] = 3，sum = 9，堆变成四个元素 {1, 2, 3, 3}，超过 k，弹出堆顶 1，sum = 8，堆是 {2, 3, 3}。此时 nums2[1] = 1，分数为 $8 \times 1 = 8$，小于 12，答案不变。

返回 12，对应选择下标 0、2、3：nums1 之和为 $1 + 3 + 2 = 6$，nums2 最小值为 $\min(2, 3, 4) = 2$，分数 12，与预期一致。

再看 k = 1 的用例 nums1 = [4, 2, 3, 1, 1]、nums2 = [7, 5, 10, 9, 6]，预期 30。按 nums2 降序的下标顺序是 2（10）、3（9）、0（7）、4（6）、1（5）。处理下标 2 时堆里只有 nums1[2] = 3，sum = 3，大小已等于 1，分数 $3 \times 10 = 30$，答案 30。之后每一步都会先压入再弹出，堆里始终只留当前最大的一个 nums1 值：处理下标 3 时留下 3、分数 $3 \times 9 = 27$；处理下标 0 时 4 挤掉 3、分数 $4 \times 7 = 28$；处理下标 4 时仍是 4、分数 24；处理下标 1 时仍是 4、分数 20。最大值 30，正确。

若把小顶堆错写成大顶堆，第一个例子在处理下标 1 时会弹掉 3 而不是 1，sum 变成 6，虽然本例答案不受影响，但在 nums1 = [1, 100]、k = 1 这类数据上会立刻把最大的 100 扔掉，答案严重偏小。

代码实现

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();
            }
            // 此刻 nums2[i] 正是堆内所有位置中 nums2 的最小值。
            if (heap.size() == k) {
                answer = Math.max(answer, sum * nums2[i]);
            }
        }
        return answer;
    }
}

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())
        }
        // 此刻 nums2[i] 正是堆内所有位置中 nums2 的最小值。
        if len(minHeap) == k {
            if cand := sum * int64(nums2[i]); cand > answer {
                answer = cand
            }
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n \log n)$。按 nums2 降序排序下标是 $O(n \log n)$；随后单趟遍历中每个元素至多入堆一次、出堆一次，每次堆操作是 $O(\log k)$，合计 $O(n \log k)$。由于 $k \le n$，整体由排序主导，是 $O(n \log n)$。

空间复杂度：$O(n)$。下标数组占 $O(n)$，堆最多装 $k + 1$ 个元素占 $O(k)$，排序的额外开销在 Java 中因对象数组走归并排序而是 $O(n)$、在 Go 中是 $O(\log n)$ 的递归栈。

关键点总结

目标函数含有「极值因子」时，标准破法是把极值从未知量变成枚举量：枚举谁是那个最小值，剩下的部分就退化成一个无耦合的简单最优化问题。这条思路可以直接迁移到「和乘以最小值」「和乘以最大值」「区间长度乘以最小值」等一大类题目。

枚举顺序要与「候选池单调扩张」对齐。按 nums2 降序遍历，使得「已处理集合」恰好等于「合法候选集合」，从而把每次 $O(n)$ 的重新筛选压成 $O(\log k)$ 的增量维护。

维护「前 k 大之和」的标准工具是小顶堆：堆顶是候选中的最小者，也就是下一个该被淘汰的。想清楚「谁该被淘汰」再选堆的方向，比死记「求前 k 大用小顶堆」更可靠。

堆的内容与累加器必须严格同步：入堆即加、出堆即减，两个动作成对出现。一旦脱节，后续所有分数都是错的且难以定位。

排序时要搬动下标而非数值，因为两个数组通过下标绑定。凡是「多个数组按位置配对」的题，第一反应就该是对下标排序或先打包成结构体。

数值范围要在动手前估算：本题和最大 $10^{10}$、乘积最大 $10^{15}$，必须全程 64 位。返回值类型是长整型这一点，本身就是题目给出的溢出提示。

面试视角：先说明「顺序无关，本质是选子集」，再指出两个因子方向相反、无法单独贪心，然后抛出「枚举最小值」这一步——这是整道题的题眼，说出来基本就通过了。接着讲降序遍历如何让候选池单调扩张，最后给出小顶堆的增量维护。面试官常追问「为什么只在堆满 k 个时才更新答案」，答案是不足 k 个时选择不合法；再追问「nums2 有重复值会不会出问题」，回答是不会——相同 nums2 值的位置内部顺序任意，因为它们对应的右因子相同，而左因子只会随候选池扩张而不减。

解法对比

朴素枚举子集：正确但完全不可行。它的价值仅在于说明「两个因子必须联合考虑」，可以作为讲解的起点，但绝不能作为提交答案。

只按 nums1 或只按 nums2 单向贪心：写起来最短，但都是错的。前者会选中 nums2 极小的位置拖垮右因子，后者会选中 nums1 极小的位置拖垮左因子。面试中若脱口而出这类做法，最好紧跟一句反例说明自己知道它为什么错。

排序 + 小顶堆：$O(n \log n)$ 时间、$O(n)$ 空间，是本题的标准解，也是面试官期待的答案。它把一个二元耦合的最优化问题拆成「枚举一维、增量维护另一维」，结构清晰且常数很小。

排序 + 前缀式的其他维护方式：有人会想把堆换成「排序后取前 k 大」的静态预处理，但候选池是随遍历动态扩张的，静态方案需要对每个前缀重新求前 k 大，反而更慢。也有人尝试用平衡树或有序集合替代堆，复杂度相同但常数更大、代码更长，除非还需要中位数之类的额外查询，否则没有必要。

面试怎么答：开口先讲「枚举最小值」的思路而不是直接背代码，因为这一步才是考点；讲完思路再说「候选池随降序遍历单调扩张，所以用小顶堆增量维护前 k 大之和」；最后主动补一句溢出风险和 64 位类型。整套讲下来大约两分钟，比先写代码再解释更容易让人跟上。

易错点总结

错误写法：用大顶堆，弹出堆顶时扔掉的是最大值。用例 nums1 = [1, 100]、nums2 = [1, 1]、k = 1 → 处理第二个位置时把 100 弹出、留下 1，答案算成 1，正确答案是 100。

错误写法：sum 用 32 位整型。用例：$10^5$ 个值为 $10^5$ 的元素、k = 10^5 → 和达到 $10^{10}$，32 位下溢出成负数，乘积随之为负，答案完全错误。

错误写法：乘法写成 (int) sum * nums2[i] 或两个 32 位数直接相乘。用例 nums1 与 nums2 各取 $10^5$ 量级、k 较大 → 乘积达 $10^{15}$，在 32 位下截断，返回一个看似合理的小数字。

错误写法：按 nums2 升序排序。用例 nums1 = [1, 3, 3, 2]、nums2 = [2, 1, 3, 4]、k = 3 → 处理到某个位置时，已处理集合是「nums2 不大于当前值」的那些，右因子不再等于 nums2[i]，分数计算的前提被破坏，答案与 12 不符。

错误写法：把答案更新写在弹出堆顶之前。用例 nums1 = [1, 3, 3, 2]、nums2 = [2, 1, 3, 4]、k = 3 → 处理下标 1 时堆里有 4 个元素、sum = 9，算出 $9 \times 1 = 9$，这个分数对应选了 4 个位置，不合法。

错误写法：弹出堆顶时忘记从 sum 中减去。用例 nums1 = [1, 3, 3, 2]、nums2 = [2, 1, 3, 4]、k = 3 → sum 一路累加成 9 而堆里只有 3 个元素，后续所有分数都被高估。

错误写法：排序数值本身而不是下标。用例 nums1 = [1, 3, 3, 2]、nums2 = [2, 1, 3, 4]、k = 3 → 单独对 nums2 排序后两个数组的配对关系被打乱，nums1[i] 与 nums2[i] 不再属于同一个位置，结果毫无意义。

错误写法：比较器写成 nums2[a] - nums2[b] 却期望降序。用例：任意数据 → 得到的是升序，与上面「按升序排序」的后果相同，答案偏小。

错误写法：只在遍历到第 k 个元素时更新一次答案，之后不再更新。用例 nums1 = [4, 2, 3, 1, 1]、nums2 = [7, 5, 10, 9, 6]、k = 1 → 只算了第一个位置的 30 就停手，虽然本例恰好正确，但换成最优解出现在后面的数据（比如后半段有很大的 nums1 值）就会漏掉更优分数。

错误写法：把答案初始化成一个负的哨兵值并在堆不足 k 时也更新。用例 nums1 = [1, 2]、nums2 = [3, 4]、k = 2 → 堆只有 1 个元素时就用 sum * nums2[i] 更新，得到一个用 1 个位置算出的分数，违反「恰好选 k 个」的约束。

错误写法：认为「nums1 前 k 大」可以先整体排序一次性确定。用例 nums1 = [5, 1, 1]、nums2 = [1, 9, 9]、k = 2 → 全局前 2 大是 5 和 1（下标 0 与 1），分数 $6 \times 1 = 6$；而正确答案是选下标 1、2，分数 $2 \times 9 = 18$。候选池必须随最小值的枚举动态变化。

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	只求单个第 K 大而非前 K 之和，可用大小为 K 的小顶堆，也可用快速选择
703. 数据流中的第 K 大元素	简单	同样用小顶堆维护「当前前 K 大」，但数据在线到达，没有排序这一预处理步骤
347. 前 K 个高频元素	中等	排序键是频次而非原值，考点在于统计与选取的衔接，无二元乘积的耦合
786. 第 K 个最小的质数分数	中等	同样是两数组配对成的目标值，但要按值排名而非求最大，需用堆或二分答案
632. 最小区间	困难	目标同样含极值因子，用堆管一端、变量管另一端，是「枚举一维」思路的另一形态
1675. 数组的最小偏移量	困难	极差作为目标，靠归一化把操作变单向后用堆逐步压低最大值
1648. 销售价值减少的颜色球	中等	堆的贪心因操作次数过大而失效，改用二分水平线批量结算，是本题堆解法的反例
2462. 雇佣 K 位工人的总代价	中等	同样要在动态候选池里取最优 K 个，但候选来自双端窗口，需要两个堆配合指针