leetcode：871.最低加油次数【以前pat做过+最大堆+贪心】

分析

注意&＃xff0c;加油站是沿途&＃xff0c;所以target一定在所有加油站的右方
然后&＃xff0c;油的效果是累计的&＃xff0c;根跳跃游戏不一样&＃xff0c;不能走一下贪心一下
要用一个大根堆维护之前的加油中最大的加油量来贪心
思想就是&＃xff0c;走到某个地方&＃xff0c;如果去到之后的油是负数&＃xff0c;那么就找之前存着的加油站中的最大值加一下&＃xff0c;计算一次
如果加完之前的所有都到不了就凉凉
然后把当前的加油站放入大根堆&＃xff08;奖励&＃xff09;&＃xff0c;并更新上一个点prev
注意&＃xff0c;target是最后一个curr&＃xff0c;也要算上去

Ac code

class Solution:def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:# 加油的效果是累计的# 所以用大根堆&＃xff0c;每次取最大的加油来贪心&＃xff08;大根堆&＃xff09;# 如果取完还不能到目前点&＃xff0c;返回-1ans, nowFuel, prev, pq &＃61; 0, startFuel, 0, []stations.sort()n &＃61; len(stations)# 多一个target的位置# 沿途右加油站&＃xff0c;所以target一定在最右边for i in range(n &＃43; 1):# 当前要去的位置curr &＃61; stations[i][0] if i < n else targetnowFuel -&＃61; curr - prev# 不够油的&＃xff0c;贪心加油while nowFuel < 0 and pq:nowFuel &＃43;&＃61; -heappop(pq)ans &＃43;&＃61; 1# 加完开始去不到if nowFuel < 0:return -1# 若能去到&＃xff0c;放进大根堆if i < n:heappush(pq, -stations[i][1])# 更新prevprev &＃61; currreturn ans


总结

贪心 &＃43; 大根堆
非常classic

20220905踩踩

这个是延迟支付的思想
去得到的先放进pq当备胎
然后产生危机的时候在备胎里面选一个加油最大的

java

class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {// b - a > 0就交换&＃xff0c;所以是大根堆PriorityQueue<Integer> pq &＃61; new PriorityQueue<Integer> ((a, b) -> b - a);int ans &＃61; 0, prev &＃61; 0, fuel &＃61; startFuel;int n &＃61; stations.length;// fuel是累计的for (int i &＃61; 0; i <&＃61; n; i&＃43;&＃43;) {int curr &＃61; i < n ? stations[i][0] : target;fuel -&＃61; curr - prev;while (fuel < 0 && !pq.isEmpty()) {fuel &＃43;&＃61; pq.poll();ans&＃43;&＃43;;}if (fuel < 0) {return -1;}if (i < n) {pq.offer(stations[i][1]);prev &＃61; curr;}}return ans;}
}


java总结

// b - a > 0就交换&＃xff0c;所以是大根堆
PriorityQueue pq &＃61; new PriorityQueue ((a, b) -> b - a);
b - a这个式子的意思是&＃xff0c;b - a > 0就交换&＃xff0c;所以是大根堆
反之&＃xff0c;如果改成a - b&＃xff0c;如果a - b > 0就交换&＃xff0c;就是小根堆
pq.isEmpty()
pq.poll()
pq.offer()