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就不能往下面走了，其实下一个元素取决于之前的元素，所以这题本质也是利用动态规划来解题： 1. 找从起点开始，能往下一直走的最远位置，即如果 sum subarray > 0，一直往下走，如果sum subarray < 0， 说明以那个起点开始走是走不通的，必须取下一个gas station 为新的起点，继续看该station能不能走得通， 一直这样找直到到最后一个gas station为止 2. 最后还需要看看我们在动态规划中找的那个start能不能走通，看从 第一个gas station 走到start的时候剩余多少gas，如果剩余量 》=0 可以走到，否则是无解的，即不能走到。

一个重要属性： 如果前面走过的gas station， 它的gas - cost < 0 ， 那么起点必须移到下一个gas station。 这样，这道题就转化成了 sum subarray > 0的问题。
下面有些变量可以省去，但是为了释义更加明显，题目思路更加清晰，还是保留下来了，也可以做点后期处理把这些不需要的变量删去。
 时间复杂度： O（n）， 空间复杂度O（n）,其实可以优化到O（1）
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //sanity check
        if (gas.size() == 0 || cost.size() == 0) return -1;
        int M[gas.size()];
        for (int i = 0; i < gas.size(); i++) {
            M[i] = gas[i] - cost[i];
        }
        //subarray sum
        int M1[gas.size()];
        M1[0] = M[0];
        int start = 0;
        for (int i = 1; i <  gas.size(); i++) {
            if (M1[i-1] < 0) {
                M1[i] = M[i];
                start = i;
            } else {
                M1[i] = M1[i-1] + M[i];
            }
        }
        int sum = 0;
        for (int i = 0; i < start; i++) {
            sum += M[i];
        }
        if (sum + M1[gas.size()-1] >= 0) return start;
        else return -1;
    }
};

updated: 空间复杂度： O(1)

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //sanity check
        if (gas.size() == 0 || cost.size() == 0) return -1;
        //subarray sum
        int M1 = gas[0] - cost[0];
        int pre = gas[0] - cost[0];
        int start = 0;
        for (int i = 1; i <  gas.size(); i++) {
            if (pre < 0) {
                M1 = gas[i] - cost[i];
                start = i;
            } else {
                M1 = pre +gas[i] - cost[i];
            }
            pre = M1;
        }
        int sum = 0;
        for (int i = 0; i < start; i++) {
            sum += gas[i] - cost[i];
        }
        if (sum + M1 >= 0) return start;
        else return -1;
    }
};