题目描述
思路解析动画文字版
记住「左右各取 candidates 个进最小堆 → 每轮弹堆顶最低 → 从弹出那侧补一个」,下面每一帧都在套它。
开局候选池是空的。左指针在最左 0、右指针在最右 8。先从左边连取 4 个工人放进最小堆。
从左边取下标 0 的工人(成本 17)放进候选池。左指针右移到 1。
从左边取下标 1 的工人(成本 12)放进候选池。左指针右移到 2。
从左边取下标 2 的工人(成本 10)放进候选池。左指针右移到 3。
从左边取下标 3 的工人(成本 2)放进候选池。左指针右移到 4。
从右边取下标 8 的工人(成本 8)放进候选池。右指针左移到 7。
从右边取下标 7 的工人(成本 20)放进候选池。右指针左移到 6。
从右边取下标 6 的工人(成本 11)放进候选池。右指针左移到 5。
从右边取下标 5 的工人(成本 2)放进候选池。右指针左移到 4。
候选池建好了,共 8 个候选;中间灰色那段还没进过池。每一轮就弹一次堆顶(成本最低、同成本下标小),开始雇人。
第 1 轮雇人:候选池里成本最低的是下标 3 的工人(成本 2、和另一个成本 2 并列,按下标小的先选),雇下他(绿色),总代价加到 2。他来自左侧。接下来按规则从左侧补一个新候选进池。
从左侧补一个:下标 4 的工人(成本 7)进池,候选池又回到 8 个,留给下一轮挑。
第 2 轮雇人:候选池里成本最低的是下标 5 的工人(成本 2),雇下他(绿色),总代价加到 4。他来自右侧。此时两端候选已取光(left=5 > right=4),不再补新人,后面直接从池里弹最低。
这时 left=5 已经越过 right=4,两端候选取光、没有新人可补,候选池剩 7 个,下一轮直接从池里弹最低。
第 3 轮雇人:候选池里成本最低的是下标 4 的工人(成本 7),雇下他(绿色),总代价加到 11。他来自左侧。这已是第 3 个、k 人凑满,算法到此停止、不再补人。
第 3 个人也雇好了,k 人已凑满,代码到这就停止,不会再雇了。此时 left=5 也已经越过 right=4,本就没有新人可补。
雇满 3 人,依次是成本 2、2、7,加起来最小总代价 11。靠「两端候选 + 最小堆 + 弹一个补一个」,每轮都全局取到当前能选的最低成本,不用反复扫整排。
边界:候选覆盖整排=纯最小堆;k=n 雇光;补位永远同侧,left > right 后就不再补、只弹。
面试常考:相遇后只弹不补;堆里存下标用于平局与判侧。
参考代码
from typing import Listimport heapqclass Solution: def totalCost(self, costs: List[int], k: int, candidates: int) -> int: n = len(costs) heap = [] left, right = 0, n - 1 for _ in range(candidates): if left <= right: heapq.heappush(heap, (costs[left], left, 0)) left += 1 for _ in range(candidates): if left <= right: heapq.heappush(heap, (costs[right], right, 1)) right -= 1 ans = 0 for _ in range(k): cost, idx, side = heapq.heappop(heap) ans += cost if left <= right: if side == 0: heapq.heappush(heap, (costs[left], left, 0)) left += 1 else: heapq.heappush(heap, (costs[right], right, 1)) right -= 1 return ans复杂度
- 时间：O((candidates + k) log candidates)，堆里最多 2·candidates 个元素;初始化逐个入堆是 O(candidates log candidates),之后每轮一次弹出加一次插入各 O(log candidates)、共 k 轮
- 空间：O(candidates)，最小堆最多装两端各 candidates 个候选
易错点
面试追问把动画讲成自己的话
追问左右指针相遇(left > right)后还怎么继续雇人?
追问为什么候选元素要把下标也存进堆?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大子序列分数
LeetCode 2542 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题