Leetcode 134 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.

贪心，我的做法是将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:

• If there is only one gas station, it’s true.
• If there are two gas stations a and b, and gas(a) cannot afford cost(a), i.e., gas(a) < cost(a), then gas(b) must be greater than cost(b), i.e., gas(b) > cost(b), since gas(a) + gas(b) > cost(a) + cost(b); so there must be a way too.
• If there are three gas stations a, b, and c, where gas(a) < cost(a), i.e., we cannot travel from a to b directly, then:
• either if gas(b) < cost(b), i.e., we cannot travel from b to c directly, then cost(c) > cost(c), so we can start at c and travel to a; since gas(b) < cost(b), gas(c) + gas(a) must be greater than cost(c) + cost(a), so we can continue traveling from a to b. Key Point: this can be considered as there is one station at c’ with gas(c’) = gas(c) + gas(a) and the cost from c’ to b is cost(c’) = cost(c) + cost(a), and the problem reduces to a problem with two stations. This in turn becomes the problem with two stations above.
• or if gas(b) >= cost(b), we can travel from b to c directly. Similar to the case above, this problem can reduce to a problem with two stations b’ and a, where gas(b’) = gas(b) + gas(c) and cost(b’) = cost(b) + cost(c). Since gas(a) < cost(a), gas(b’) must be greater than cost(b’), so it’s solved too.
• For problems with more stations, we can reduce them in a similar way. In fact, as seen above for the example of three stations, the problem of two stations can also reduce to the initial problem with one station.

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();
    }
};