LeetCode 2462. 雇佣 K 位工人的总代价
题目描述
题意分析
共雇佣
k轮，每轮只允许在尚未雇佣工人的最前candidates人与最后candidates人中，选择费用最低的一人；费用相同，选择位置更靠前者。雇佣后该人移除，下一轮候选范围随剩余队列变化。两端候选可能重叠，同一个人只能算一次；剩余不足候选数时，所有剩余工人都可选。返回累计费用，不要求返回雇佣名单，不能直接将全部费用排序后取最便宜的
k人。
解法：两端候选堆与中间补充指针
核心思路
[!blue]
用两个小根堆分别保存当前从左端、右端进入候选范围的费用。
i、j指向尚未加入任何堆的中间区间[i, j]；堆中的人已经可选，中间的人还未解锁，三部分始终互不重复。初始化先从左边取至多
candidates人，再从右边取同样数量，但右指针不能越过左指针。这样即使两个候选范围重叠，也只会将每个人加入一次；中间为空时，两个堆的并集已经包含全部剩余工人。每轮只需比较两个堆顶，就能得到全部合法候选中的最低费用。左堆的原位置都在右堆之前，删除其他人不会改变这种相对顺序，所以跨堆费用相同应选择左堆；某个堆为空时只能从另一侧选。
从左堆雇佣一人后，前端候选空出一个位置，中间最左侧的
costs[i]成为新的前端候选，因此只向左堆补一个；右侧同理补costs[j]。中间已经为空就不再补，两堆随剩余人数一起缩小。堆内只保存费用即可。同一侧有多个等费工人时，取走哪一份费用，都会让该侧费用多重集合减少同一个值，并解锁同一个中间边界工人；两侧的前后位置关系也不改变。虽然无需记录堆内具体身份，仍能得到题目要求的总代价。
每轮只移除一人并保持上述候选划分，执行恰好
k轮。总费用最多达到百亿量级，累计值使用 Java 的long或 Go 的int64。
解题步骤
- 初始化左右小根堆和未入堆区间
[i, j]，先填左侧，再在不重复的前提下填右侧。- 每轮比较有效堆顶，费用相等选左侧，某侧为空则选另一侧。
- 弹出所选费用并计入 64 位总和。
- 若
i <= j，从刚选中的同一侧补入一个中间工人，并移动对应边界。- 完成
k轮后返回总费用。
代码实现
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
int n = costs.length;
PriorityQueue<Integer> left = new PriorityQueue<>();
PriorityQueue<Integer> right = new PriorityQueue<>();
int i = 0;
int j = n - 1;
while (i < candidates) {
left.offer(costs[i++]);
}
// j >= i 防止把 left 已经收走的人重复压进 right，重叠情形靠它兜住。
while (j >= i && n - 1 - j < candidates) {
right.offer(costs[j--]);
}
// 总和量级 1e10，必须用 long。
long ans = 0;
for (int t = 0; t < k; t++) {
// 相等时取左边，即「代价相同选下标更小者」。
if (right.isEmpty() || (!left.isEmpty() && left.peek() <= right.peek())) {
ans += left.poll();
// 中间地带 [i, j] 还有人才补，补完窗口大小恢复。
if (i <= j) {
left.offer(costs[i++]);
}
} else {
ans += right.poll();
if (i <= j) {
right.offer(costs[j--]);
}
}
}
return ans;
}
}
import (
"container/heap"
)
func totalCost(costs []int, k int, candidates int) int64 {
n := len(costs)
left, right := &IntHeap{}, &IntHeap{}
i, j := 0, n-1
for i < candidates {
heap.Push(left, costs[i])
i++
}
// j >= i 防止把 left 已经收走的人重复压进 right，重叠情形靠它兜住。
for j >= i && n-1-j < candidates {
heap.Push(right, costs[j])
j--
}
// 总和量级 1e10，必须用 int64。
var ans int64
for t := 0; t < k; t++ {
// 相等时取左边，即「代价相同选下标更小者」。
if right.Len() == 0 || (left.Len() > 0 && (*left)[0] <= (*right)[0]) {
ans += int64(heap.Pop(left).(int))
// 中间地带 [i, j] 还有人才补，补完窗口大小恢复。
if i <= j {
heap.Push(left, costs[i])
i++
}
} else {
ans += int64(heap.Pop(right).(int))
if i <= j {
heap.Push(right, costs[j])
j--
}
}
}
return ans
}
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
复杂度分析
记
c = candidates。
- 时间复杂度：$O((c + k)\log(c + 1))$。当前实现逐个压入初始化候选，之后每轮弹出一次、最多补入一次，每个堆大小不超过
c。- 空间复杂度：$O(\min(n, 2c))$，两个堆只保存互不重叠的已解锁候选。
关键点总结
[!green]
- 左堆、尚未解锁的中间区间、右堆共同描述当前状态，任何人只能属于其中一处。
- 从哪一侧取人，就只从那一侧解锁下一人。
- 跨堆平局选左来自位置先后；同堆等费身份不影响费用集合的后续变化。
- 中间区间耗尽后只弹出不补充，重叠和人数不足无需重复建候选。
易错点总结
[!yellow]
- 两端初始候选重叠时重复压入，会让同一工人被雇佣两次。
- 从选中侧的反方向补人，会改变下一轮合法候选范围。
- 两侧费用相等时选右，可能解锁不同的后续工人，导致总代价错误。
- 中间已耗尽仍继续补入，会重复使用或越界读取工人。
- 全局取最便宜的若干人忽略了候选范围限制；总和也不能使用 32 位整数累计。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 373. 查找和最小的 K 对数字 | 中等 | 同样维护多个有序来源的当前候选，每次弹出后只补充相关来源，本题来源由数组两端动态推进。 |
| 215. 数组中的第K个最大元素 | 中等 | 同样用堆选择较小或较大元素，本题候选会随选择动态解锁，不能静态取前k。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！