LeetCode 134. 加油站

这题的证明挺有意思的,可以看一下官方题解。

从某一个车站出发,只要到最后一个车站的油够用,并且全程的油耗加起来大于等于0,那么从该车站出发就能走一圈。


C++代码:

class Solution {

public:

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int res = 0;

        int sum = 0;

        int cur_tank = 0;

        for(int i = 0; i < gas.size(); i++){

            sum += (gas[i] - cost[i]);

            cur_tank += (gas[i] - cost[i]);

            if(cur_tank < 0){

                cur_tank = 0;

                res = i + 1;

            }

        }

        if(sum < 0 || res == gas.size()) return -1;

        return res;

    }

};

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。