程式小試身手

cars=[2,10,8,17], k=3

這題我原本以為是排序後取三蓋屋頂,排序[2,8,10,17] ,210 得 10-2+1=9

結果還要考慮取最小間距 

cars=[1,7,9,10,11], k=3 ,19 得9-1+1=9 但實際應為 11-9+1=3

看到解答用PriorityQueue,很少用反而學習到,總之是把最小放最前,poll取最前並刪除

Collections.reverseOrder() 反轉,最大放最前

public static long carParkingRoof(List<Long> cars, int k) {
 // Write your code here
 if (cars.size() == 0 k < 0) {
 return 0;
 }

 PriorityQueue<Long> maxHeap = new PriorityQueue<Long>(k, Collections.reverseOrder()); 

 long minSlot = Long.MAX_VALUE;

 for (long carSlot : cars) {
 maxHeap.offer(carSlot);
 
 minSlot = Math.min(minSlot, carSlot);

 if (maxHeap.size() > k) {
 maxHeap.poll();
 }
 }

 return maxHeap.poll() - minSlot + 1;
 }