最大子序列分数 图解题解
这道题到底在问什么
- 输入
- nums1=[6,6,2,1,1,7,1,7], nums2=[4,5,9,5,5,4,9,6], k=3
- 输出
- 80
先想最直接的笨办法
先把八对 (nums2, nums1) 按 nums2 从大到小排成右边这张表:nums2 依次是 9、9、6、5、5、5、4、4。从上往下扫时,扫到哪一对,那一对的 nums2 就是「目前这一批里最小的 nums2」,这正是枚举最小值的妙处。（动画第 4 步）
最优解：一步一步想明白
- 3记住这条主线:按 nums2 降序扫,当前 nums2 就是这批的最小值;最小堆只留 nums1 最大的 k 个、保证和最大;堆满 k 时算一次分数。下面每一帧都在套它。
- 4先把八对 (nums2, nums1) 按 nums2 从大到小排成右边这张表:nums2 依次是 9、9、6、5、5、5、4、4。从上往下扫时,扫到哪一对,那一对的 nums2 就是「目前这一批里最小的 nums2」,这正是枚举最小值的妙处。
- 5第 1 对:nums2=9、nums1=2。把 nums1=2(紫色)压进最小堆,nums1 之和 total += 2 → 2。当前堆里有 1 个,还没超过 k=3。
- 6堆里现在 1 个,还不够 k=3,暂时算不出完整分数(必须凑满 k 个才有「这批的最小值乘和」)。继续往下扫:nums2 会变小,但 nums1 之和有机会变大。
- 7第 2 对:nums2=9、nums1=1。把 nums1=1(紫色)压进最小堆,nums1 之和 total += 1 → 3。当前堆里有 2 个,还没超过 k=3。
- 8堆里现在 2 个,还不够 k=3,暂时算不出完整分数(必须凑满 k 个才有「这批的最小值乘和」)。继续往下扫:nums2 会变小,但 nums1 之和有机会变大。
- 9第 3 对:nums2=6、nums1=7。把 nums1=7(紫色)压进最小堆,nums1 之和 total += 7 → 10。当前堆里有 3 个,还没超过 k=3。
- 10堆里正好 k=3 个、和为 10。当前这批的最小 nums2 就是 6,算一个候选分数:10 × 6 = 60。比之前的最优大,刷新答案 ans → 60。
- 11第 4 对:nums2=5、nums1=6。把 nums1=6(紫色)压进最小堆,nums1 之和 total += 6 → 16。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
- 12堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=1),total -= 1 → 15。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
- 13堆里正好 k=3 个、和为 15。当前这批的最小 nums2 就是 5,算一个候选分数:15 × 5 = 75。比之前的最优大,刷新答案 ans → 75。
- 14第 5 对:nums2=5、nums1=1。把 nums1=1(紫色)压进最小堆,nums1 之和 total += 1 → 16。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
- 15堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=1),total -= 1 → 15。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
- 16堆里正好 k=3 个、和为 15。当前这批的最小 nums2 就是 5,算一个候选分数:15 × 5 = 75。没有超过已有最优 75,答案保持不变。
- 17第 6 对:nums2=5、nums1=1。把 nums1=1(紫色)压进最小堆,nums1 之和 total += 1 → 16。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
- 18堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=1),total -= 1 → 15。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
- 19堆里正好 k=3 个、和为 15。当前这批的最小 nums2 就是 5,算一个候选分数:15 × 5 = 75。没有超过已有最优 75,答案保持不变。
- 20第 7 对:nums2=4、nums1=7。把 nums1=7(紫色)压进最小堆,nums1 之和 total += 7 → 22。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
- 21堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=2),total -= 2 → 20。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
- 22堆里正好 k=3 个、和为 20。当前这批的最小 nums2 就是 4,算一个候选分数:20 × 4 = 80。比之前的最优大,刷新答案 ans → 80。
- 23第 8 对:nums2=4、nums1=6。把 nums1=6(紫色)压进最小堆,nums1 之和 total += 6 → 26。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
- 24堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=6),total -= 6 → 20。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
- 25堆里正好 k=3 个、和为 20。当前这批的最小 nums2 就是 4,算一个候选分数:20 × 4 = 80。没有超过已有最优 80,答案保持不变。
- 26八对全扫完。最大分数出现在「最小值锁定为 4」那一批:堆里 nums1 之和 20,乘最小值 4,得 80。靠「按 nums2 降序枚举最小值 + 最小堆保留和最大的 k 个」,一次扫描就拿到答案,不用枚举所有子序列。
⚠️ 容易写错的地方
✗ 错：直接枚举所有子序列
✓ 对：排序后枚举「谁当最小值」
子序列指数级爆炸;按 nums2 降序扫,当前 nums2 自动就是这批的最小值,把问题降成一维贪心
✗ 错：堆用成大根堆,弹掉了大的
✓ 对：用最小堆,弹掉最小的 nums1
要保留 nums1 最大的 k 个让和最大,所以多出来时该淘汰最小的那个,堆顶必须是最小值
✗ 错：堆没满 k 就去算分数
✓ 对：只有堆大小等于 k 时才结算
不足 k 个不构成一个合法选法,这一批还凑不出「乘上最小值的完整分数」
✗ 错：答案用 int 存,溢出了
✓ 对：和与分数用 long / long long
nums 可达 1e5、k 可达 1e5,和能到 1e10、分数到 1e15,超出 32 位整数范围
完整代码（Python / C++ / Java）
Python
from typing import List
import heapq
class Solution:
def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
pairs = sorted(zip(nums2, nums1), reverse=True)
heap = []
total = 0
ans = 0
for b, a in pairs:
heapq.heappush(heap, a)
total += a
if len(heap) > k:
total -= heapq.heappop(heap)
if len(heap) == k:
ans = max(ans, total * b)
return ansC++
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int,int>> pairs;
for (int i = 0; i < (int)nums1.size(); ++i) pairs.push_back({nums2[i], nums1[i]});
sort(pairs.rbegin(), pairs.rend());
priority_queue<int, vector<int>, greater<int>> pq;
long long sum = 0, ans = 0;
for (auto [b, a] : pairs) {
pq.push(a); sum += a;
if ((int)pq.size() > k) { sum -= pq.top(); pq.pop(); }
if ((int)pq.size() == k) ans = max(ans, sum * b);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
int[][] pairs = new int[n][2];
for (int i = 0; i < n; i++) { pairs[i][0] = nums2[i]; pairs[i][1] = nums1[i]; }
Arrays.sort(pairs, (a,b) -> b[0] - a[0]);
PriorityQueue<Integer> pq = new PriorityQueue<>();
long sum = 0, ans = 0;
for (int[] p : pairs) {
pq.offer(p[1]); sum += p[1];
if (pq.size() > k) sum -= pq.poll();
if (pq.size() == k) ans = Math.max(ans, sum * p[0]);
}
return ans;
}
}复杂度
时间
O(n log n)
排序 n 对 O(n log n);扫描里每对一次入堆一次弹堆、堆 ≤ k,单次 O(log k)。整体由排序主导
空间
O(n)
pair 数组 O(n),最小堆最多 k 个 O(k),合起来 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大子序列分数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么是「枚举最小值」而不是「枚举最大和」?+
分数是「和 × 最小值」两个量的乘积,直接同时优化很难。把其中一个固定下来(让某个 nums2 当最小值),另一个就变成单纯的「在受限集合里取 nums1 之和最大的 k 个」,这是一个有现成贪心解的子问题。按 nums2 降序扫,就把所有可能的最小值都枚举了一遍。
堆里的元素为什么只存 nums1、不存 nums2?+
当前这批的最小 nums2 已经由「扫到的当前那一对」唯一确定了,不需要再从堆里取。堆只负责回答「这批里 nums1 之和最大的 k 个是多少」,所以只存 nums1 值;再维护一个 total 累加和,弹出时减去堆顶即可,连求和都不用每次重扫。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大子序列分数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。