描述

在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。

请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。
题目数据可以保证最多有一个答案。

数据范围： 1 \le n \le 10^4 \1≤n≤104  ， gas 和 cost 数组中的值满足 1 \le val \le 10^5 \1≤val≤105 

示例1

输入： 
[1,2,3,4,5],[3,4,5,1,2]
复制
返回值： 
3
复制
说明： 
只能从下标为 3 的加油站开始完成 （即第四个加油站）

示例2

输入： 
[0,10],[9,1]
复制
返回值： 
1
复制
解题思路
1、因为题目数据量比较大，暴力解法应该会超时，所以先观察是否有规律可循；
2、可以看到要能满足题目要求，出发站的汽油gas[i]肯定需要大于从i到i+1需要消耗的汽油，即cost[i]，利用这个规律剪枝；
3、另外要注意对环路的处理，本题中使用cnt统计路过的加油站，确保从某一出发点出发后n个加油站都遍历到 

class Solution {
public:
    bool func(vector<int>& gas, vector<int>& cost, int index) {
        int n = gas.size();
        int cnt = 0;
        int sum = 0;
        for (int i = index; cnt < n; i++) {
            sum += (gas[i%n] - cost[i%n]);
            if (sum < 0) return false;
            cnt++;
        }
        return (sum >= 0);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    int gasStation(vector<int>& gas, vector<int>& cost) {
        // write code here
        int n = gas.size();
        bool flag = false;
        for (int i = 0; i < n; i++) {
            if (gas[i] < cost[i]) {
                continue;
            }
            flag = func(gas, cost, i);
            if (flag) return i;
        }
        return -1;
    }
};