-
Notifications
You must be signed in to change notification settings - Fork 0
/
GasStation.cpp
41 lines (32 loc) · 1.06 KB
/
GasStation.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
Problem: Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
Solution: Queue
Time Complexity: O(n)
Space Complexity: O(1)
*/
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int start=0;
int end=1;
int n=gas.size();
int curr=gas[start]-cost[start];
while(end!=start||curr<0){
while(curr<0&&start!=end){
curr-=gas[start]-cost[start];
start=(start+1)%n;
if(start==0){
return -1;
}
}
curr+=gas[end]-cost[end];
end=(end+1)%n;
}
return start;
}
};