题目描述
思路解析动画文字版
记住这条主线:按 nums2 降序扫,当前 nums2 就是这批的最小值;最小堆只留 nums1 最大的 k 个、保证和最大;堆满 k 时算一次分数。下面每一帧都在套它。
先把八对 (nums2, nums1) 按 nums2 从大到小排成右边这张表:nums2 依次是 9、9、6、5、5、5、4、4。从上往下扫时,扫到哪一对,那一对的 nums2 就是「目前这一批里最小的 nums2」,这正是枚举最小值的妙处。
第 1 对:nums2=9、nums1=2。把 nums1=2(紫色)压进最小堆,nums1 之和 total += 2 → 2。当前堆里有 1 个,还没超过 k=3。
堆里现在 1 个,还不够 k=3,暂时算不出完整分数(必须凑满 k 个才有「这批的最小值乘和」)。继续往下扫:nums2 会变小,但 nums1 之和有机会变大。
第 2 对:nums2=9、nums1=1。把 nums1=1(紫色)压进最小堆,nums1 之和 total += 1 → 3。当前堆里有 2 个,还没超过 k=3。
堆里现在 2 个,还不够 k=3,暂时算不出完整分数(必须凑满 k 个才有「这批的最小值乘和」)。继续往下扫:nums2 会变小,但 nums1 之和有机会变大。
第 3 对:nums2=6、nums1=7。把 nums1=7(紫色)压进最小堆,nums1 之和 total += 7 → 10。当前堆里有 3 个,还没超过 k=3。
堆里正好 k=3 个、和为 10。当前这批的最小 nums2 就是 6,算一个候选分数:10 × 6 = 60。比之前的最优大,刷新答案 ans → 60。
第 4 对:nums2=5、nums1=6。把 nums1=6(紫色)压进最小堆,nums1 之和 total += 6 → 16。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=1),total -= 1 → 15。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
堆里正好 k=3 个、和为 15。当前这批的最小 nums2 就是 5,算一个候选分数:15 × 5 = 75。比之前的最优大,刷新答案 ans → 75。
第 5 对:nums2=5、nums1=1。把 nums1=1(紫色)压进最小堆,nums1 之和 total += 1 → 16。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=1),total -= 1 → 15。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
堆里正好 k=3 个、和为 15。当前这批的最小 nums2 就是 5,算一个候选分数:15 × 5 = 75。没有超过已有最优 75,答案保持不变。
第 6 对:nums2=5、nums1=1。把 nums1=1(紫色)压进最小堆,nums1 之和 total += 1 → 16。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=1),total -= 1 → 15。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
堆里正好 k=3 个、和为 15。当前这批的最小 nums2 就是 5,算一个候选分数:15 × 5 = 75。没有超过已有最优 75,答案保持不变。
第 7 对:nums2=4、nums1=7。把 nums1=7(紫色)压进最小堆,nums1 之和 total += 7 → 22。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=2),total -= 2 → 20。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
堆里正好 k=3 个、和为 20。当前这批的最小 nums2 就是 4,算一个候选分数:20 × 4 = 80。比之前的最优大,刷新答案 ans → 80。
第 8 对:nums2=4、nums1=6。把 nums1=6(紫色)压进最小堆,nums1 之和 total += 6 → 26。当前堆里有 4 个,超过了 k=3,接下来弹掉最小的一个。
堆里已经 4 个,超过 k=3。弹掉堆顶(最小的 nums1=6),total -= 6 → 20。这样堆里始终只留 nums1 最大的 3 个,保证它们的和最大;新顶(绿色)是当前这 3 个里最小的。
堆里正好 k=3 个、和为 20。当前这批的最小 nums2 就是 4,算一个候选分数:20 × 4 = 80。没有超过已有最优 80,答案保持不变。
八对全扫完。最大分数出现在「最小值锁定为 4」那一批:堆里 nums1 之和 20,乘最小值 4,得 80。靠「按 nums2 降序枚举最小值 + 最小堆保留和最大的 k 个」,一次扫描就拿到答案,不用枚举所有子序列。
边界:k=1 取单点乘积最大;k=n 唯一一种选法;nums2 全相等时退化成纯取 nums1 最大的 k 个。
面试常考:为什么枚举最小值(把乘积拆成可贪心的子问题)、堆为什么只存 nums1(最小值已被当前对锁定)。
参考代码
from typing import Listimport heapqclass 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 ans复杂度
- 时间：O(n log n)，排序 n 对 O(n log n);扫描里每对一次入堆一次弹堆、堆 ≤ k,单次 O(log k)。整体由排序主导
- 空间：O(n)，pair 数组 O(n),最小堆最多 k 个 O(k),合起来 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么是「枚举最小值」而不是「枚举最大和」?
追问堆里的元素为什么只存 nums1、不存 nums2?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
合并 K 个升序链表
LeetCode 23 · 困难 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题