分析
- 双端选择策略：
- 使用两个最小堆分别管理两端候选工人的代价：
- 左堆
left_heap：存储前 candidates 个工人
- 右堆
right_heap：存储后 candidates 个工人
- 每轮从两堆中选择代价最小的工人。如果代价相同，优先选择左堆的工人（即下标较小的工人）
- 动态维护候选集合：
- 每次从堆中弹出一个工人后：
- 如果是左堆弹出，在左堆加入新的候选工人（如果剩余工人足够）
- 如果是右堆弹出，在右堆加入新的候选工人（如果剩余工人足够）
- 模拟雇佣过程：
- 进行
k 轮雇佣，每轮计算当前最小代价并累加到总成本
时间复杂度
- 初始化堆：最多处理
2 * candidates 个工人，复杂度为 O(candidates * log candidates)
- 每次雇佣需要从堆中弹出元素并可能插入一个新元素，复杂度为
O(log candidates)
- 总共雇佣
k 轮，因此雇佣过程的复杂度为 O(k * log candidates)
总时间复杂度：O((k + candidates) * log candidates)
空间复杂度
- 使用两个最小堆，每个堆最多存储
candidates 个元素
总空间复杂度：O(candidates)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution
{
public:
long long totalCost(vector<int>& costs, int k, int candidates)
{
// 左、右堆分别维护前 candidates 和后 candidates 个工人的代价
std::priority_queue<int, std::vector<int>, std::greater<int>> left_heap, right_heap;
int l = 0, r = costs.size() - 1;
// 初始化左堆
for (int i = 0; i < candidates && l <= r; ++i, ++l)
left_heap.push(costs[l]);
// 初始化右堆
for (int i = 0; i < candidates && l <= r; ++i, --r)
right_heap.push(costs[r]);
long long totalCost = 0; // 总代价
for (int i = 0; i < k; ++i)
{
// 从两堆中选择代价最小的工人
if (left_heap.size() && (right_heap.empty() || left_heap.top() <= right_heap.top()))
{
totalCost += left_heap.top(); // 累加代价
left_heap.pop(); // 移除工人
if (l <= r) // 更新左堆
left_heap.push(costs[l++]);
}
else
{
totalCost += right_heap.top(); // 累加代价
right_heap.pop(); // 移除工人
if (l <= r) // 更新右堆
right_heap.push(costs[r--]);
}
}
return totalCost; // 返回总代价
}
};
|
