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.
贪心,我的做法是将gas-cost的值求和,和小于0,则肯定不能到,大于等于0一定可以到,因为一定可以从无法通过的那段区域的下一个位置开始。
求出gas-cost和最小的位置,那么从他的下一个位置开始,必定可以通过。
然后在discuss看到了更好的做法:是否可达和我的一样,但是起始位置和我的想法不一样,
一旦发现和小于0,则把它下一个位置置为起始位置,更新tank为0,最后得到的起始位置就是结果。
因为每发现和小于0,则可以把这些加油站看作一个加油站,一直到最后只有两个两个加油站,后一个加前一个必然大于等于0!
有可能没说清楚,贴上英文原文解释:
Proof to the first point: say there is a point C between A and B -- that is A can reach C but cannot reach B. Since A cannot reach B, the gas collected between A and B is short of the cost. Starting from A, at the time when the car reaches C, it brings in gas >= 0, and the car still cannot reach B. Thus if the car just starts from C, it definitely cannot reach B.
Proof for the second point:
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int sum = 0, minn = INT_MAX, pos;
for(int i = 0;i < gas.size();i++)
{
sum+=(gas[i]-cost[i]);
if(minn > sum)
{
minn = sum;
pos = i;
}
}
if(sum<0) return -1;
return (pos+1) % gas.size();
}
};