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

分析

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

Ac code

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        # 加油的效果是累计的
        # 所以用大根堆，每次取最大的加油来贪心（大根堆）
        # 如果取完还不能到目前点，返回-1

        ans, nowFuel, prev, pq = 0, startFuel, 0, []
        stations.sort()
        n = len(stations)

        # 多一个target的位置
        # 沿途右加油站，所以target一定在最右边
        for i in range(n + 1):
            # 当前要去的位置
            curr = stations[i][0] if i < n else target
            nowFuel -= curr - prev
            # 不够油的，贪心加油
            while nowFuel < 0 and pq:
                nowFuel += -heappop(pq)
                ans += 1
            
            # 加完开始去不到
            if nowFuel < 0:
                return -1
            
            # 若能去到，放进大根堆
            if i < n:
                heappush(pq, -stations[i][1])
                # 更新prev
                prev = curr
        
        return ans

总结

贪心 + 大根堆
非常classic