134 - Gas Station

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.
Hide Tags
Greedy
 
很显然期待的答案不是直接从每个起点都走一圈，要贪心。
怎么个贪法呢？
一开始想错了，跑去算了所有的差值，从差值最大的下标开始，看起来似乎是贪心了，
但问题是，起点虽然差值最大，但下一个，下下一个可不一定差值就是第二第三大，所以还是超时了。。。
看别人写的分析，一句话就戳破了窗户纸：
“当到达某一站点时，若这个值小于0了，则说明从起点到这个点中间的任何一个点都不能作为起点”（原帖在此）
这应该就是这道题的题眼了！！
重新按照这个思路写了代码，果然顺利通过。
 
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int gz=gas.size(), cz=cost.size(), rst=-1;
        if(gz == cz)
        {
            for(int start=0; start<gz; ++start)
            {
                int balance=0, newstart=start;
                for( ; newstart<(cz+start); ++newstart)
                {
                    int idx = (newstart >= cz) ? (newstart-cz) : newstart;
                    balance += (gas[idx] - cost[idx]);
                    if(0 > balance)
                        break;
                }
                if(0>balance)
                    start = newstart;
                else
                    return start;
            }
        }
        return -1;
    }
};
8 ms.