Sponsored
Sponsored
This approach leverages a greedy strategy with a max heap to ensure that whenever we're out of fuel, we choose to refuel from the station that offers the most fuel, maximizing our reach.
We traverse through the list of stations, when we reach a station, we check if we need to refuel (i.e., if our current fuel can't get us to the next station). If so, we refuel from the stations we've passed (choosing the one with the most fuel available). We keep track of the number of stops and return that as our result once we reach the target, or return -1 if it's not possible to reach the target.
Time Complexity: O(n log n), as each insertion into the heap takes O(log n), and we perform this operation n times.
Space Complexity: O(n), storing the maximum fuel to be reused in a max-heap equivalent array.
1#include <stdio.h>
2#include <stdlib.h>
3
4int minRefuelStops(int target, int startFuel, int** stations, int stationsSize)
This C solution uses an array to mimic a max-heap, replacing the max-heap functionality with a manually sorted insertion. Fuel from each station is added to the heap whenever it is reachable. We keep refueling from the station with maximum fuel until we reach the target or run out of options.
In this approach, we use dynamic programming to track the maximum distance reached with a given number of refuel stops. By simulating the range expansions step-by-step at each station, we keep updating our maximum reach for each refuel stop count.
This works by creating an array dp where dp[i] stands for the farthest distance we can reach with i stops. Initially, dp[0] is initialized with startFuel, and the rest are kept at zero. As we iterate through the stations, we update this dp array backwards so as not to overwrite data prematurely. For each station, we update the dp array to reflect the best possible distance for each number of stops, which includes potentially refueling at that station.
Time Complexity: O(n^2), as each station iterates over previous positions in potentially worst-case scenarios.
Space Complexity: O(n), where n is the station count and the dp array stores potential distances.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
6 vector<long> dp(stations.size() + 1, 0);
7 dp[0] = startFuel;
8
9 for (int i = 0; i < stations.size(); ++i) {
10 for (int t = i; t >= 0; --t) {
11 if (dp[t] >= stations[i][0])
12 dp[t + 1] = max(dp[t + 1], dp[t] + stations[i][1]);
13 }
14 }
15
16 for (int i = 0; i <= stations.size(); ++i) {
17 if (dp[i] >= target) return i;
18 }
19 return -1;
20}
21The C++ dynamic programming solution involves a dp table storing the farthest distance that can be achieved given a fixed number of refueling stops. It updates iteratively through each station, backward to compute possibilities without prematurely ruling out achievable distances with extra gas.