LeetCode 134. 加油站

方法一：简单模拟
循环遍历两数组，从第一个满足启动的下标开始，根据解释模拟行驶情况

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int can_complete=0,len=gas.size();
    	if(len==1){//特判
			if(gas[0]>=cost[0]) return 0;
			else return -1;
		}
    	for(int i=0;i<len;i++){
			if(gas[i]>cost[i]){//能启动
				int sum=0,cnt=0,j=i;
				sum+=gas[i];
				while(sum>=cost[j%len]){//能启动
					sum=sum-cost[j%len]+gas[(j+1)%len];
					cnt++;j++;
					if(cnt>=len){//行驶一圈
						can_complete=1; break;
					}
				}
			}
			if(can_complete) return i;
		}
    	return -1;
    }
};

方法二：贪心算法

柱状图
绿色：可添加的汽油 gas[i]
橙色：消耗的汽油 cose[i]

折线图：
虚线（蓝色）：当前加油站的可用值
实线（黑色）：从0开始的总剩余汽油量

黑色折线图即总油量剩余值，若要满足题目的要求：跑完全程再回到起点，总油量剩余值的任意部分都需要在X轴以上，且跑到终点时：总剩余汽油量 $≥0$≥0。
为了让黑色折线图任意部分都在X轴以上，我们需要向上移动黑色折线图，直到所有点都在X轴或X轴以上。此时，处在X轴的点即为出发点。即黑色折线图的最低值的位置：index = 3

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
        int len=gas.size(),left_gas=0,min_gas=INFINITY,min_i=0;
		for(int i=0;i<len;i++){//遍历数组，找到最小的left_gas并记录下标min_i
			left_gas+=gas[i]-cost[i];
			if(left_gas<min_gas){
				min_gas=left_gas;
				min_i=i;
			}
		}
		return left_gas<0?-1:(min_i+1)%len;//若行驶一圈后left_gas<0，则无法行使一圈，否则起点为min_i+1
    }
};