134. 加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& g, vector<int>& c) {
        int n = g.size();
        vector<int> h(n,0);
        // h[i] -> gas change from i-1 -> i
        h[0] = g[n-1] - c[n-1];
        for (int i = 1 ; i < n ; i ++ ) {
            h[i] = g[i-1]-c[i-1];
        }
        int start = 0;
        int pos = start;
        int csum = 0;
        while (pos < start + n && start < n) {
            csum += h[(1+pos)%n];
            if (csum < 0) {
                start = pos + 1;
                csum = 0;
            }
            pos ++ ;
        }
        return start<n?start:-1;
    }
};

贪心算法（方法一） 还挺巧妙的，我这个就是个最大子数组的算法