134. 加油站

一、暴力法

从每个加油站开始模拟是否能跑完一圈
for循环遍历每个加油站，while循环模拟跑一圈

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for(int i=0;i<cost.size();i++)
        {
            //初始化第一个加油站的剩余油量
            int rest = gas[i]-cost[i];
            int index = (i+1)%cost.size();
            while(rest>0&&index!=i)
            {
                rest += gas[index]-cost[index];
                index = (index+1)%cost.size();
            }
            //index==i说明跑完了一圈
            if(rest>=0&&index==i)return i;
        }
        return -1;
    }
};

二、贪心

用currest记录当前的汽油剩余量，若小于0，说明当前位置不能作为起始位置，将当前位置的下一位置作为start
totalrest用于记录跑完一圈剩余的油量，若小于0，说明不可能跑完。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int currest = 0;
        int totalrest = 0;
        int start = 0;
        for(int i=0;i<gas.size();i++)
        {
            currest += gas[i]-cost[i];
            totalrest += gas[i]-cost[i];
            if(currest<0)
            {
                start = i+1;
                currest=0;
            }
        }
        if(totalrest<0)return -1;
        return start;
    }
};