LeetCode 134. Gas Station

思路

O(n^2)做法：直接嵌套循环，暴力试就行
O(n)做法：类似贪心的思路。主要还是看gas[i]-cost[i]，如果减出来是正的，那么可以为后面的路段留下点资源，如果减出来是负的话，那么最好的做法是在之前积累最多的资源来解决这个debt. 那什么时候有可能积累到最多资源呢？只能将这个有欠债的站点作为最后一站，所以将该站点的下一站作为起始试试。

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalLoss = 0;
        int tank = 0;
        int max_i = 0;
        for(int i=0; i<gas.size(); i++){
            tank += gas[i] - cost[i];
            if(tank < 0){   //Owe!
                max_i = i+1; //next possible start
                totalLoss += tank;  //add in the debt
                tank = 0;
            }
        }
        if(totalLoss + tank < 0)    //if the debt cannot be paid
            return -1;
        return max_i;
    }
};