LeetCode 2462. 雇佣 K 位工人的总代价

2026-07-14 HGNULB 约 13 分钟

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

分类

题目描述

✅ 2462. 雇佣 K 位工人的总代价

题意分析

一排工人站成一列，costs[i] 是雇第 i 位的代价。要进行 k 轮雇佣，每轮从队首的 candidates 人和队尾的 candidates 人这两段里挑代价最小的一位雇走；代价相同时挑原始下标更小的那位。剩余人数不足 candidates 时，就从所有剩下的人里挑最小的。返回 k 轮的代价总和。

有四点必须先钉死。第一，每轮的候选范围是动态的：某人被雇走后队列缩短，下一轮的「前 candidates 人」会自动补进来一位新面孔，所以候选窗口是随雇佣推进而移动的。第二，两段窗口可能重叠：当 2 * candidates >= n 时，前后两段覆盖了整个队列甚至有交集，此时同一个人不能被当成两个候选重复参与，题面在样例 1 的第三轮和样例 2 的第一轮都特意点出了这一点。第三，平局规则是按原始下标比，不是按「当前在队列中的位置」；不过因为下标小的人永远排在下标大的人前面，用原始下标判断和用当前位置判断是一致的。第四，一个人只能被雇一次。

约束是 1 <= costs.length <= 10^5、1 <= costs[i] <= 10^5、1 <= k, candidates <= costs.length。规模说明每轮不能重新扫一遍候选段，否则最坏 $O(nk)$ 会到 $10^{10}$。代价上界给出了溢出信号：总和最大约 $10^5 \times 10^5 = 10^{10}$，超过 32 位整数上限，返回值必须是 64 位 —— 题目把返回类型定成 long 就是在提醒这件事。

边界有三种：2 * candidates >= n（两段一开始就覆盖全体，等价于「取全数组最小的 k 个」）、k == n（所有人都要雇，答案就是全部代价之和）、以及 n == 1 这种最小规模。这三种都不该靠特判硬扛，好的写法应该让它们自然落入主逻辑。

解法：双指针 + 前后两个小根堆

核心思路

暴力是每轮扫一遍前 candidates 个和后 candidates 个找最小值，再把人从数组里删掉，$O(k \cdot candidates)$ 加上删除的搬移开销，最坏 $10^{10}$，超时。瓶颈很典型：每轮都在同一批几乎没变的候选人里从头找最小值，上一轮辛苦比较出来的次序信息全被扔掉了。

关键观察有两层。第一层：需要的操作是「反复取最小、偶尔加入一个新元素」，这正是小根堆的主场，取最小从 $O(candidates)$ 降到 $O(\log candidates)$，补人也是 $O(\log candidates)$。第二层：前后两段必须用两个独立的堆，不能合成一个。因为补人的来源不同 —— 从前段雇走一人后，补进来的是队首窗口右边的下一位（下标增大的方向）；从后段雇走一人后，补进来的是队尾窗口左边的下一位（下标减小的方向）。两个方向由两个指针 i 和 j 分别推进，堆也就必须分开，否则根本说不清该往哪边补。

于是维护的不变量是：left 堆装着队首窗口中尚未被雇的全部工人，right 堆装着队尾窗口中尚未被雇的全部工人，两堆内容互不相交；i 是前段下一个待入堆的下标，j 是后段下一个待入堆的下标，闭区间 [i, j] 是既未入堆也未被雇的「中间地带」。每轮取两个堆顶中较小的一个，雇走后从中间地带补一个进对应的堆，i 右移或 j 左移，中间地带随之收缩。

重叠问题就是靠这条不变量解决的。初始化时先把前 candidates 个压入 left（i 停在 candidates），再从队尾往前压 right，但必须同时满足「压够 candidates 个」和「j >= i」两个条件，后者保证不去碰已经被 left 收走的人。当 2 * candidates >= n 时，j 会在压够之前就跌到 i 以下而提前停止，两个堆合起来恰好装下全部 n 个人且不重不漏 —— 「窗口覆盖全体」这种情况因此不需要任何特判，自动退化成「从全体里连取 k 个最小值」。

补人同样受 i <= j 保护：中间地带空了就不补，堆只出不进，直到取满 k 次。k 不会超过 n，所以永远有人可取，不必担心两个堆同时为空。

平局规则则由比较方向兜住：取堆顶时用 left.peek() <= right.peek()，相等时优先取左边。因为 left 里的下标恒小于 right 里的下标，这个「小于等于」正好实现了「代价相同选下标更小者」。至于同一个堆内部的平局，两人代价本来就相等，选谁对总代价没有影响，不必额外记录下标。

解题步骤

记 n = costs.length，建两个小根堆 left、right，令 i = 0、j = n - 1。为什么：两段的补人方向相反，必须各用一个堆和一个指针；i 和 j 相向而行，它们之间就是尚未参与的中间地带。

把 costs[i] 依次压入 left 直到 i 等于 candidates。为什么：队首窗口就是下标 [0, candidates) 这一段，压完后 i 自然停在下一个待补的位置上。

当 j >= i 且已压入 right 的数量不足 candidates 时，把 costs[j] 压入 right 并让 j 左移。为什么：前一个条件防止把 left 已经收走的人重复计入，这是应对「前后窗口重叠」的唯一手段；后一个条件保证窗口大小不超标。

循环 k 轮。每轮若 right 为空，或 left 非空且 left.peek() <= right.peek()，就从 left 取；否则从 right 取。为什么：两个堆顶分别是两段的最小值，全局最小必居其一；取等号时偏向 left，正是「代价相同取下标更小」的落实；right 为空的判断保证末期只剩一侧时仍能正常取。

取出的代价累加进一个 64 位的答案变量。为什么：k 与 costs[i] 都可达 $10^5$，总和量级 $10^{10}$，32 位整数会回绕。

每次取完后，若 i <= j，就把中间地带对应端点的人补进刚被取空一位的那个堆：从 left 取就补 costs[i] 并让 i 右移，从 right 取就补 costs[j] 并让 j 左移。为什么：窗口大小要保持为 candidates；i <= j 的判断保证中间地带耗尽后不再补，也不会越界或重复。

k 轮结束后返回累计和。为什么：每轮恰好雇一人，k 轮正好雇满 k 位。

以 costs = [17,12,10,2,7,2,11,20,8]、k = 3、candidates = 4 走一遍：n = 9，期望答案 11。

初始化：left 压入下标 0 到 3，即 {17,12,10,2}，i 停在 4。right 从 j = 8 往前压，依次压入 8（下标 8）、20（下标 7）、11（下标 6）、2（下标 5），压满 4 个后停止，j 停在 4。此时中间地带是 [4, 4]，只剩下标 4 的工人 7 还没入堆。

第一轮：left 堆顶是 2（下标 3），right 堆顶是 2（下标 5），两者相等，按 <= 取左边 —— 正是题面说的「选下标更小的第 3 位工人」。总代价 0 + 2 = 2。因为 i = 4 <= j = 4，把 costs[4] = 7 补进 left，i 变 5。中间地带现在空了（i = 5 > j = 4）。

第二轮：left 是 {7,10,12,17}，堆顶 7；right 是 {2,8,11,20}，堆顶 2。7 <= 2 不成立，从 right 取 2，总代价 2 + 2 = 4。此时 i > j，不再补人。

第三轮：left 堆顶仍是 7，right 变成 {8,11,20}、堆顶 8。7 <= 8 成立，从 left 取 7，总代价 4 + 7 = 11。注意这位工人下标为 4，在剩余队列里同时属于前四人和后四人 —— 我们的两个堆天然不会把他数两遍，因为他只被压进过 left。返回 11，与期望一致。

重叠边界用样例 2 复核：costs = [1,2,4,1]、k = 3、candidates = 3。left 压入下标 0 到 2 得 {1,2,4}，i = 3。right 从 j = 3 开始，j >= i 成立，压入 costs[3] = 1，j 变 2；此时 j = 2 < i = 3，虽然只压了 1 个（不足 candidates）也必须停 —— 若不判 j >= i，下标 2 和 1 的工人会被重复压进 right。第一轮两堆堆顶都是 1，取左边（下标 0），总代价 1，i > j 不补；第二轮 left 堆顶 2、right 堆顶 1，取右边，总代价 2；第三轮 right 已空，从 left 取 2，总代价 4。与期望一致，且「剩余不足 candidates 就从所有剩下的人里挑」这条规则并未单独写代码，是自动满足的。

代码实现

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, 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;
    }
}

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
}

复杂度分析

时间复杂度：$O((c + k) \log c)$，其中 $c = candidates$。初始化最多压入 $2c$ 个元素（受 $n$ 限制），每次 $O(\log c)$；随后 $k$ 轮，每轮一次弹出加至多一次压入，也是 $O(\log c)$。由于 $c \le n$ 且 $k \le n$，最坏为 $O(n \log n)$，相比暴力的 $O(k \cdot c)$（最坏 $10^{10}$）降了一个数量级以上。

空间复杂度：$O(\min(n, 2c))$，两个堆各装至多 $c$ 个元素，且两者合计不超过 $n$；除此之外只有两个指针和一个累加变量，与 $k$ 无关。

关键点总结

「反复取最小 + 动态补充」就是堆的定义式场景。识别信号是「每轮从一个会变化的候选集合里挑最优」，一旦看到就不要再写「每轮重新扫描」，那等于把上一轮的比较结果全丢掉。

补充方向不同，就必须用不同的堆。这题最容易犯的结构性错误是把前后候选合成一个堆，结果雇走一人后不知道该从哪边补。判断依据是「元素来源是否共享同一个推进方向」，方向不同就拆开维护。

用一个「中间地带」区间统一表达剩余资源。[i, j] 既是补人的取数来源，也是「还有没有人可补」的判定依据，两个指针相向收缩，重叠、耗尽、越界三类问题被同一个条件 i <= j 一并解决 —— 这比为每种情况写特判可靠得多。

让特殊情况自然落入主逻辑，而不是加分支。2 * candidates >= n、k == n、n == 1 都没有单独的代码路径，全靠初始化时的 j >= i 和补人时的 i <= j 兜住。特判越少，出错的角落越少。

平局规则要落到比较符上。因为 left 的下标恒小于 right，把 < 写成 <= 就完整实现了「代价相同选下标更小」，不需要在堆里额外存下标做二级比较 —— 先想清楚数据的固有顺序，往往能省掉一整套比较器。

面试视角：这题面试官最爱问的两点，一是「前后窗口重叠了怎么办」，回答要具体到「初始化 right 时加 j >= i 判断」，并现场用 costs = [1,2,4,1]、candidates = 3 举例说明不加会怎样；二是「返回值为什么是 long」，要能立刻算出 $10^5 \times 10^5 = 10^{10}$ 超过 int 上限。若还有时间，可以主动提一句：当 2 * candidates >= n 时其实退化成「取全数组最小的 k 个」，说明你理解了算法的边界行为而不只是背了模板。

易错点总结

答案用 int 累加：costs 为 $10^5$ 个 100000、k = 100000、candidates = 1 → 输出 1410065408，正确答案是 10000000000。所有官方样例的和都是个位数，这个 bug 只有大数据才现形，而它恰恰是本题设置 long 返回值的原因。

初始化 right 时不判 j >= i：costs = [3,7,5,2]、k = 2、candidates = 4 → 输出 4，正确答案是 5。下标 3 的工人 2 同时被压进了两个堆，于是被「雇」了两次。样例 1 因为 2 * candidates < n 完全测不出来，样例 2 又恰好因为数值相同而蒙对，是本题最隐蔽的错误。

补人时不判 i <= j：costs = [1,2,4,1]、k = 3、candidates = 3 → 输出 3，正确答案是 4。中间地带早已耗尽，却还往堆里塞已经被雇走或根本不存在的人，轻则算错、重则数组越界。

平局时取右边（把 left.peek() <= right.peek() 写成 <）：costs = [2,4,4,1,1,2]、k = 3、candidates = 1 → 输出 4，正确答案是 5。这一轮两边代价相同、当轮代价没差别，但雇走的人不同，后续几轮的候选集合随之整体偏移，总和就跟着错了。别以为「反正值一样、选谁都行」—— 平局规则影响的是之后的候选范围。两个官方样例都测不出这条。

忘了判断某个堆为空就直接 peek：末期中间地带耗尽、某一侧被取光后，peek 会返回空引用并抛异常。k 轮总能取满是因为 k <= n，但「某一侧先空」是常态，两个空判断都得写。

用一个堆存 (代价, 下标) 二元组，靠下标区分前后段：思路看似统一，但雇走一人后无法判断该从哪个方向补人 —— 需要额外维护「这个下标属于前段还是后段」的映射，代码反而更长更易错。前后拆成两个堆才是自然的建模。

每轮重新构造堆或重新扫描候选段：结果正确但退化到 $O(k \cdot c)$，$10^5$ 规模直接超时。堆的价值在于跨轮复用，一旦每轮重建就等于白用了这个结构。

把工人从数组里真的删掉来模拟队列缩短：每次删除都要搬移 $O(n)$ 个元素，总复杂度 $O(nk)$。队列的缩短应该用两个指针表达，而不是真的动数据。

误以为「剩余不足 candidates」需要单独写一个分支：加了特判反而容易和主逻辑冲突，出现同一个人既在特判分支里被取、又留在堆里的情况。这条规则由 i <= j 自动满足，多写的分支只会制造 bug。

right 的入堆条件写成 n - 1 - j <= candidates：多压一个人进后段窗口，窗口大小变成 candidates + 1，某些数据下会挑到本不该在候选范围内的工人。边界的开闭要照着「窗口恰好 candidates 人」逐字核对。

相似题目

题目	难度	考察点
1046. 最后一块石头的重量	简单	单个堆的反复取最值与放回，没有窗口与补人逻辑，可用来单独熟悉优先队列的基本节奏
373. 查找和最小的 K 对数字	中等	同样是「取一个最小值后按固定规则补入下一个候选」，但补人方向由二维下标决定，需要额外判重
23. 合并 K 个升序链表	困难	多路归并的经典形态，堆里同时存 `k` 条链的当前头，取走谁就从谁那条链补，与本题的双路补人同构
502. IPO	困难	双堆配合但分工不同：一个堆按资本排序做「解锁」，另一个堆按利润取最大，考察的是两堆之间的流动
2542. 最大子序列的分数	中等	同样用小根堆维护固定大小的集合，但堆的作用是「淘汰最差的」而非「选出最优的」，目标函数也复杂得多