LeetCode算法题(Go语言实现)_52

题目

给你一个下标从 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 位工人的总代价。

一、代码实现（Go语言）

import (
	"container/heap"
	"sort"
)

type element struct {
	cost  int
	index int
}

type MinHeap []element

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool {
	if h[i].cost == h[j].cost {
		return h[i].index < h[j].index
	}
	return h[i].cost < h[j].cost
}
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(element)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func totalCost(costs []int, k int, candidates int) int {
	n := len(costs)
	if candidates*2+k > n {
		sorted := make([]int, n)
		copy(sorted, costs)
		sort.Ints(sorted)
		sum := 0
		for i := 0; i < k; i++ {
			sum += sorted[i]
		}
		return sum
	}

	frontHeap, backHeap := &MinHeap{}, &MinHeap{}
	heap.Init(frontHeap)
	heap.Init(backHeap)

	i, j := candidates, n-candidates-1
	for idx := 0; idx < candidates; idx++ {
		heap.Push(frontHeap, element{cost: costs[idx], index: idx})
	}
	for idx := 0; idx < candidates; idx++ {
		pos := n - 1 - idx
		heap.Push(backHeap, element{cost: costs[pos], index: pos})
	}

	total := 0
	for k > 0 {
		k--
		var current element
		useFront := false

		if frontHeap.Len() > 0 && backHeap.Len() > 0 {
			frontTop := (*frontHeap)[0]
			backTop := (*backHeap)[0]
			if frontTop.cost < backTop.cost || (frontTop.cost == backTop.cost && frontTop.index < backTop.index) {
				current = heap.Pop(frontHeap).(element)
				useFront = true
			} else {
				current = heap.Pop(backHeap).(element)
			}
		} else if frontHeap.Len() > 0 {
			current = heap.Pop(frontHeap).(element)
			useFront = true
		} else {
			current = heap.Pop(backHeap).(element)
		}

		total += current.cost

		if useFront {
			if i <= j {
				heap.Push(frontHeap, element{cost: costs[i], index: i})
				i++
			}
		} else {
			if j >= i {
				heap.Push(backHeap, element{cost: costs[j], index: j})
				j--
			}
		}
	}
	return total
}

二、算法分析

1. 核心思路

• 双最小堆优化：使用两个最小堆分别管理前 candidates 和后 candidates 的候选工人，按代价和索引排序，确保快速取出最小值。
• 动态指针扩展：通过指针 i 和 j 动态扩展候选范围，前堆从左侧扩展，后堆从右侧收缩，避免重复处理元素。
• 特殊情况优化：当候选范围覆盖整个数组时（candidates*2 +k >n），直接排序取前 k 小元素之和。

2. 关键步骤

1. 预处理特殊情况：若候选范围能覆盖所有选择，直接排序取前 k 小元素。
2. 堆初始化：前堆和后堆分别存储初始候选元素。
3. 层级处理：每次从堆顶取最小值，更新指针并扩展候选范围，直到完成 k 次选择。
4. 边界处理：确保指针移动时不会交叉，避免重复处理元素。

3. 复杂度

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 全候选覆盖：直接排序取最小 k 个元素。
• 指针交叉：停止扩展候选，仅处理堆中剩余元素。
• 索引冲突：优先选择索引更小的元素。

2. 扩展应用

• 动态数据流：支持实时插入新工人并调整堆结构。
• 多维度排序：增加工作经验、评级等指标作为次要排序条件。

3. 多语言实现

import heapq

def totalCost(costs, k, candidates):
    n = len(costs)
    if candidates * 2 + k > n:
        return sum(sorted(costs)[:k])
    
    front = [(costs[i], i) for i in range(candidates)]
    heapq.heapify(front)
    back = [(costs[n-1-i], n-1-i) for i in range(candidates)]
    heapq.heapify(back)
    
    i, j = candidates, n - candidates - 1
    total = 0
    
    for _ in range(k):
        if not front and not back:
            break
        f_min = front[0] if front else (float('inf'), -1)
        b_min = back[0] if back else (float('inf'), -1)
        
        if f_min[0] < b_min[0] or (f_min[0] == b_min[0] and f_min[1] < b_min[1]):
            total += heapq.heappop(front)[0]
            if i <= j:
                heapq.heappush(front, (costs[i], i))
                i += 1
        else:
            total += heapq.heappop(back)[0]
            if j >= i:
                heapq.heappush(back, (costs[j], j))
                j -= 1
                
    return total

五、总结与优化

1. 算法对比

2. 工程优化

• 堆结构压缩：用元组 (cost, index) 替代对象，减少内存占用。
• 并行处理：多线程维护前堆和后堆的插入操作。
• 预计算优化：预处理部分候选范围以减少堆操作次数。

3. 扩展方向

• 多级候选策略：分层选择候选（如先选区域再选具体工人）。
• 动态调整候选数：根据剩余工人数量动态调整 candidates 值。