雇佣 K 位工人的总代价

难度: Medium

给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：

总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
- 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [3,2,7,7,1,2] 。
- 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[3,2,7,7,2] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
一位工人只能被选择一次。

返回雇佣恰好 k 位工人的总代价。

示例 1：

输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
输出：11
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
- 第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人。总代价是 0 + 2 = 2 。
- 第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。
- 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。
总雇佣代价是 11 。

示例 2：

输入：costs = [1,2,4,1], k = 3, candidates = 3
输出：4
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
- 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。
- 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。
- 第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。
总雇佣代价是 4 。

提示：

1 <= costs.length <= 10⁵
1 <= costs[i] <= 10⁵
1 <= k, candidates <= costs.length

Submission

运行时间: 107 ms

内存: 24.9 MB

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        left = 0
        right = len(costs)-1
        cost_sum = 0

        left_heap = copy.deepcopy(costs[0:candidates])
        left = candidates-1
        right_heap = copy.deepcopy(costs[max(candidates,len(costs)-candidates):])
        right = max(candidates,len(costs)-candidates)
        

        heapify(left_heap)
        heapify(right_heap)
        
        for i in range(k):
            left_min = 1e5 + 1
            right_min = 1e5+1
            if len(left_heap):
                left_min = left_heap[0]
            if len(right_heap):
                right_min = right_heap[0]
            if left_min <= right_min:
                cost_sum += left_min
                heappop(left_heap)
                if left < right-1:
                    left+=1
                    heappush(left_heap, costs[left])
            else:
                cost_sum += right_min
                heappop(right_heap)
                if right > left + 1:
                    right -= 1
                    heappush(right_heap, costs[right])
        return cost_sum

Explain

该题解的思路是使用两个最小堆（left_heap和right_heap）来分别管理数组costs中的前candidates个元素和后candidates个元素。每次迭代中，从这两个堆中找出最小的元素，然后将其从堆中移除，并将其加入到总的代价中。同时，堆从costs中继续添加新的元素以保持堆的大小为candidates，直到完成k次选择。通过这种方式，可以有效地在每一轮中找到最小代价的工人并加以雇佣。

时间复杂度: O(k log(candidates))

空间复杂度: O(candidates)

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        left = 0
        right = len(costs)-1
        cost_sum = 0

        # 初始化两个堆，分别存储前candidates个和后candidates个元素
        left_heap = copy.deepcopy(costs[0:candidates])
        left = candidates-1
        right_heap = copy.deepcopy(costs[max(candidates,len(costs)-candidates):])
        right = max(candidates,len(costs)-candidates)
        

        # 对两个堆进行堆化处理
        heapify(left_heap)
        heapify(right_heap)
        
        for i in range(k):
            left_min = 1e5 + 1
            right_min = 1e5+1
            if len(left_heap):
                left_min = left_heap[0]
            if len(right_heap):
                right_min = right_heap[0]
            if left_min <= right_min:
                cost_sum += left_min
                heappop(left_heap)
                if left < right-1:
                    left+=1
                    heappush(left_heap, costs[left])
            else:
                cost_sum += right_min
                heappop(right_heap)
                if right > left + 1:
                    right -= 1
                    heappush(right_heap, costs[right])
        return cost_sum

Explore

使用两个最小堆是为了能够高效地从`candidates`个候选者中选出最小的元素。最小堆可以在常数时间O(1)内得到最小元素，并且在对数时间O(log n)内进行插入和删除操作。这使得每次选择操作都能快速进行。虽然也可以考虑使用排序数组或平衡二叉搜索树，但在动态更新（即添加或删除元素）时，最小堆提供了更优的性能。排序数组虽然可以快速访问最小元素，但插入和删除操作平均需要O(n)时间。平衡二叉搜索树虽然提供了O(log n)的插入、删除和查找时间，但实现复杂度高于最小堆。因此，最小堆在本问题中是最合适的选择。

堆的初始化首先将`costs`数组中前`candidates`个元素和后`candidates`个元素分别放入两个最小堆中，并进行堆化处理。这样，两个堆的根节点即是各自堆中的最小值。在每次选择工人时，比较两个堆的根节点，选择其中较小的一个，然后将其从堆中移除。移除操作后，为保持堆的大小为`candidates`，会从`costs`数组中相应地向堆中添加新的元素。这种方式确保了每轮都可以从当前候选的前`candidates`和后`candidates`中选出最小代价的工人。

当`costs`数组长度小于两倍`candidates`时，前`candidates`个元素和后`candidates`个元素会有重叠。在这种情况下，可以选择将整个`costs`数组放入一个最小堆中。由于数组长度小于两倍`candidates`，这意味着所有元素都是候选元素。因此，每次从堆中取出最小元素即可，直到完成k次选择。这种方法简化了处理过程，同时依旧保证了每次都能选出当前代价最小的工人。