-
Notifications
You must be signed in to change notification settings - Fork 0
/
gas-station.cc
36 lines (36 loc) · 936 Bytes
/
gas-station.cc
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
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int len = gas.size();
int i = 0, remain = 0, start = 0;
map<int, vector<int>> res;
while(true) {
if (res.find(i) != res.end() && res[i].size() != 0) {
auto ires = res[i];
if (i != start && (ires[0] >= start && ires[0] < i)) {
return start;
} else {
remain += ires[1];
i = (ires[0] + 1) % len;
continue;
}
}
int diff = gas[i] - cost[i];
if (remain + diff < 0) {
if (res.find(start) != res.end()) return -1;
if (start != i) {
res[start] = {(len + i - 1) % len, remain};
} else {
res[start] = {};
}
i = (i + 1) % len;
start = i;
remain = 0;
} else {
remain += diff;
i = (i + 1) % len;
if (i == start) return i;
}
}
}
};