老司机加油算法
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 134. Gas Station | 🟠 |
Today, we'll share a story about a greedy old driver, which is related to LeetCode problem #134, "Gas Station":
134. Gas Station | 力扣 | LeetCode |
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique
Example 1:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Output: 3 Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.
Example 2:
Input: gas = [2,3,4], cost = [3,4,3] Output: -1 Explanation: You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 3 + 2 = 3 Travel to station 1. Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can't travel around the circuit once no matter where you start.
Constraints:
n == gas.length == cost.length1 <= n <= 1050 <= gas[i], cost[i] <= 104
The problem should be easy to understand. At each station i, you can refuel gas[i] liters of gas, but you need to consume cost[i] liters of gas to leave station i. The question is, from which station can you start and return to the starting point after a full circle?
Talking about the brute-force solution, it's quite straightforward. You can use a for loop to iterate through all stations, assuming each as a starting point, and then nest another for loop to check if you can complete a circle and return to the starting point:
int n = gas.length;
for (int start = 0; start < n; start++) {
for (int step = 0; step < n; step++) {
int i = (start + step) % n;
tank += gas[i];
tank -= cost[i];
// determine if the gas in the tank is exhausted
}
}Clearly, the time complexity is O(N^2), and such a brute-force solution is obviously not optimal. Let's try to analyze if there's room for optimization.
Is there any redundant computation in the brute-force approach? Can we abstract the concept of "state"? Are we recalculating the same "state" multiple times?
As mentioned in our previous article Dynamic Programming Explained, the changing variables are the "states". Observing this brute-force enumeration process, we see two changing variables: the "starting point" and the "current fuel level in the tank". However, the combination of these two states definitely exceeds O(N^2) possibilities, indicating no apparent room for optimization.
Therefore, solving this problem is not about simply pruning to optimize the efficiency of the brute-force method, but rather discovering some deeper hidden patterns to reduce redundant calculations.
Next, we introduce two clever methods to solve this problem: the mathematical graphical method and the greedy algorithm.
Graphical Method
When a car enters station i, it can add gas[i] fuel (green numbers in the diagram). Leaving the station consumes cost[i] fuel (red numbers in the diagram). We can consider the station and the connecting road as a whole, treating gas[i] - cost[i] as the net fuel change when passing through station i (orange numbers in the diagram):
Thus, the scenario described in the problem is abstracted into a circular array, where the i-th element is gas[i] - cost[i].
With this circular array, we need to determine if there exists a starting point start such that the cumulative sum from this starting point is always greater than or equal to 0.
How do we determine if such a starting point start exists? And how do we calculate the value of this starting point start?
Let's start with 0 as the initial point, and the code for calculating the cumulative sum is quite simple:
int n = gas.length, sum = 0;
for (int i = 0; i < n; i++) {
// calculate the cumulative sum
sum += gas[i] - cost[i];
}In the above code, the sum variable represents the change in the fuel level in the tank. For example, given this set of test cases:
gas = [4,3,1,2,7,4]
cost = [1,2,7,3,2,5]The changes in sum would look like this:
Can you determine which gas station to start from based on this graph?
Obviously, starting at 0 is not feasible because sum becomes less than 0 during the process, which does not meet our requirement that the "cumulative sum must always be greater than or equal to 0."
If 0 cannot be the starting point, which station can be?
Looking at the graph, the lowest point is the most likely candidate for the starting point:
If we take this "lowest point" as the starting point, it means treating this point as the origin of the coordinate axis, which is equivalent to "maximally" shifting the graph upwards.
Since the array is circular, the part of the graph to the left of the lowest point can be attached to the rightmost part of the graph:
This way, the entire graph stays above the x-axis, so this lowest point 4 is the starting point required by the problem.
However, does the graph always stay above the x-axis after shifting? Not necessarily, because there are cases with no solution:
If sum(gas[...]) < sum(cost[...]), meaning the total amount of fuel is less than the total consumption, it is impossible to visit all stations.
Based on the above analysis, we can write the code:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// equivalent to the coordinates and the lowest point in the image
int sum = 0, minSum = 0;
int start = 0;
for (int i = 0; i < n; i++) {
sum += gas[i] - cost[i];
if (sum < minSum) {
// after passing the i-th station, sum reaches a new low
// therefore, the station i + 1 is the lowest point (starting point)
start = i + 1;
minSum = sum;
}
}
if (sum < 0) {
// total gas is less than total consumption, no solution
return -1;
}
// characteristics of circular array
return start == n ? 0 : start;
}
}class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
// equivalent to the coordinates and the lowest point in the image
int sum = 0, minSum = 0;
int start = 0;
for (int i = 0; i < n; i++) {
sum += gas[i] - cost[i];
if (sum < minSum) {
// after passing the i-th station, sum reaches a new low
// hence, the station i + 1 is the lowest point (starting point)
start = i + 1;
minSum = sum;
}
}
if (sum < 0) {
// total gas is less than total consumption, no solution
return -1;
}
// characteristic of circular array
return start == n ? 0 : start;
}
};class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
# equivalent to the coordinate points and the lowest point in the image
sum, minSum = 0, 0
start = 0
for i in range(n):
sum += gas[i] - cost[i]
if sum < minSum:
# after passing the i-th station, sum reaches a new low
# therefore, the station i + 1 is the lowest point (starting point)
start = i + 1
minSum = sum
if sum < 0:
# total gas is less than total consumption, no solution
return -1
# characteristic of circular array
return 0 if start == n else startfunc canCompleteCircuit(gas []int, cost []int) int {
n := len(gas)
// equivalent to the coordinates and the lowest point in the image
sum, minSum, start := 0, 0, 0
for i := 0; i < n; i++ {
sum += gas[i] - cost[i]
if sum < minSum {
// after passing the i-th station, sum reaches a new low
// therefore, the station i + 1 is the lowest point (starting point)
start = i + 1
minSum = sum
}
}
if sum < 0 {
// total gas is less than total consumption, no solution
return -1
}
// characteristic of circular array
return start % n
}var canCompleteCircuit = function(gas, cost) {
let n = gas.length;
// equivalent to the coordinate points and the lowest point in the image
let sum = 0, minSum = 0;
let start = 0;
for (let i = 0; i < n; i++) {
sum += gas[i] - cost[i];
// after passing the i-th station, sum reaches a new low
if (sum < minSum) {
// therefore, the station i + 1 is the lowest point (starting point)
start = i + 1;
minSum = sum;
}
}
// total gas is less than total consumption, no solution
if (sum < 0) {
return -1;
}
// characteristic of circular array
return (start === n) ? 0 : start;
};The above solution is derived from observing the function's graph, with a time complexity of O(N), which is much more efficient than the brute-force approach.
Next, we introduce a solution using a greedy approach, which is similar to the previous one but with a different analysis process.
Greedy Solution
The key to solving this problem with a greedy approach lies in the following conclusion:
If choosing station i as the starting point 'just' fails to reach station j, then any station k between i and j cannot be a starting point.
For example, if starting from station 1 and reaching station 5 results in the fuel tank 'just' becoming negative, it means station 1 'just' cannot reach station 5. Therefore, starting from any of stations 2, 3, 4 will also fail to reach 5, as the fuel tank will inevitably become negative upon reaching station 5.
How to prove this conclusion?
Assume tank records the current fuel level. If starting from station i (tank = 0) and reaching j results in tank < 0, it means that at any station k between i and j, tank > 0, right?
If k is chosen as the starting point, it means tank = 0 at station k, and upon reaching j, tank < 0 will definitely occur, indicating that k cannot be a starting point.
Come on, if starting from i and reaching k with tank > 0 still fails to reach j, now with tank = 0, it's even more impossible to reach j, right?
Thus, this conclusion is proven.
Recall how the brute-force approach at the beginning worked?
If I find that starting from i cannot reach j, then obviously i cannot be the starting point.
Now, we've discovered a new rule. What can it deduce?
If I find that starting from i cannot reach j, then i and all stations between i and j cannot be starting points.
See the redundant calculations? See the optimization point?
This is the essence of the greedy approach: if you can't find repeated calculations, reduce redundant calculations through some deeper hidden rules in the problem.
Based on this conclusion, the following code can be written:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += gas[i] - cost[i];
}
if (sum < 0) {
// total gas is less than total cost, no solution
return -1;
}
// record the amount of gas in the tank
int tank = 0;
// record the starting point
int start = 0;
for (int i = 0; i < n; i++) {
tank += gas[i] - cost[i];
if (tank < 0) {
// cannot reach i + 1 from start
// therefore, station i + 1 should be the starting point
tank = 0;
start = i + 1;
}
}
return start == n ? 0 : start;
}
}class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int sum = 0;
for (int i = 0; i < n; i++) {
sum += gas[i] - cost[i];
}
if (sum < 0) {
// total gas is less than total cost, no solution
return -1;
}
// record the amount of gas in the tank
int tank = 0;
// record the starting point
int start = 0;
for (int i = 0; i < n; i++) {
tank += gas[i] - cost[i];
if (tank < 0) {
// cannot reach i + 1 from start
// therefore, station i + 1 should be the starting point
tank = 0;
start = i + 1;
}
}
return start == n ? 0 : start;
}
};class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
sum = 0
for i in range(n):
sum += gas[i] - cost[i]
if sum < 0:
# total gas is less than total cost, no solution
return -1
# record the amount of gas in the tank
tank = 0
# record the starting point
start = 0
for i in range(n):
tank += gas[i] - cost[i]
if tank < 0:
# cannot reach i + 1 from start
# therefore, station i + 1 should be the starting point
tank = 0
start = i + 1
return 0 if start == n else startfunc canCompleteCircuit(gas []int, cost []int) int {
n := len(gas)
sum := 0
for i := 0; i < n; i++ {
sum += gas[i] - cost[i]
}
if sum < 0 {
// total gas is less than total cost, no solution
return -1
}
// record the amount of gas in the tank
tank := 0
// record the starting point
start := 0
for i := 0; i < n; i++ {
tank += gas[i] - cost[i]
if tank < 0 {
// cannot reach i + 1 from start
// therefore, station i + 1 should be the starting point
tank = 0
start = i + 1
}
}
if start == n {
return 0
}
return start
}var canCompleteCircuit = function(gas, cost) {
var n = gas.length;
var sum = 0;
for (var i = 0; i < n; i++) {
sum += gas[i] - cost[i];
}
if (sum < 0) {
// total gas is less than total consumption, no solution
return -1;
}
// record the amount of gas in the tank
var tank = 0;
// record the starting point
var start = 0;
for (var i = 0; i < n; i++) {
tank += gas[i] - cost[i];
if (tank < 0) {
// cannot reach i + 1 from start
// therefore, the station i + 1 should be the starting point
tank = 0;
start = i + 1;
}
}
return start === n ? 0 : start;
};This solution also has a time complexity of O(N), differing from the previous graphical approach in terms of thinking process, but the code is very similar.
Actually, you can combine this solution's approach with graphical thinking. You'll find that they are essentially the same, just different in understanding.
For this kind of greedy algorithm, there isn't a particularly standardized thinking framework. It mainly relies on practicing more problems and thinking deeply, abstractly associating the problem scenarios to uncover hidden patterns, thereby reducing computation and optimizing efficiency.
Alright, this is all for this problem. I hope it helps you broaden your thinking.
