↓Skip to main content
  1. Posts/

LeetCode-871 最低加油次数

·1 min·
Table of Contents

LeetCode-871 最低加油次数 #

Solution 1 #

这道题与CodeForces-1926C2 Potions (Hard Version)非常相似, 虽然本题求的是最少加油次数, 而后者求的是最多喝药次数, 但思考逻辑是相同的. 需要尽可能少地加油, 我们考虑尽可能不加油, 计算到下一站的油量. 当油量不够时, 再从之前路过而未加加油站中选择油量最大的加上. 如果加完了油还不足以到达下一站, 则返回 $-1$ . 把终点也视作一个加油站, 便于统一处理. 代码如下:

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int ans = 0;
        vector<int> end;
        end.push_back(target);
        end.push_back(0);
        stations.push_back(end);
        priority_queue<long long> q;
        int n = stations.size();
        int fuel = startFuel;
        for (int i = 0; i < n; i++) {
            fuel -= (i == 0)? stations[i][0]: stations[i][0] - stations[i - 1][0];
            if (fuel < 0) {
                while (!q.empty() && fuel < 0) {
                    int addFuel = q.top();
                    q.pop();
                    fuel += addFuel;
                    ans++;
                }
                if (fuel < 0) {
                    return -1;
                }
            }
            q.push(stations[i][1]);
        }
        return ans;
    }
};

更新了 Python 版本的代码:

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations.append([target, 0])
        ans, cur = 0, startFuel
        h = []
        for pos, fuel in stations:
            while cur < pos and h:
                cur += -heappop(h)
                ans += 1
            if cur < pos:
                return -1
            else:
                heappush(h, -fuel)
        return ans