最小堆模拟

力扣318场周赛第三题，解法优先级队列模拟最小堆。

• 题目：
  
• 题解：

 public long totalCost(int[] costs, int k, int candidates) {
        long sum = 0,l = 0,r = costs.length - 1;
	//最小堆模拟
        PriorityQueue<Integer> left = new PriorityQueue<>(),right = new PriorityQueue<>();
        //将前candidates个加入优先级队列
        while(left.size() < candidates){
            left.offer(costs[(int)l++]);
        }
	//将后candidates个加入优先级队列，如果left区间和right区间出现碰撞，说明costs.length <= candidates
	//当出现碰撞时，因为left的已经加入过了，所以此时如果再加会变重复，又为了维持两个堆大小相同，所以此处加入最大值（因为题目要求找最小值）
        while(right.size() < candidates){
            right.offer(r < l ? Integer.MAX_VALUE : costs[(int)r--]);
        }

	//要找的次数
        for(;k>0;k--){
	   //因为题目对下标的要求仅仅是相同时取最小，所以此处直接拿最小值即可
            if(left.peek() > right.peek()){
                sum += right.poll();
		/**
		当出现碰撞时，说明两个堆中有效的数（除最大值以外的数）已经和k次遍历后数组剩余的大小相同了
		，此时避免加入重复值，所以继续加入最大值
		*/
                right.offer(r < l ? Integer.MAX_VALUE : costs[(int)r--]);
            }else{
                sum += left.poll();
		//同上，避免出现碰撞和维持大小相同
                left.offer(r < l ? Integer.MAX_VALUE : costs[(int)l++]);
            }
        }
        return sum;
    }
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