134. 加油站

• 题目描述
• 思路分析
• 代码实现

题目描述

点这里

思路分析

暴力+优化,可以理解为双指针
枚举起点 i i i,走到 j j j，如果 i i i无法走到 j j j，则 ( i , j ) (i,j) (i,j)的任何数都无法走到 j j j,证明: i i i可以走到 k k k,说明走到 k k k时剩余油 > = 0 >=0 >=0，则此后从 k k k走到 j j j的过程中时刻比一开始从 k k k走到 j j j油量多。因此，一开始从 k k k开始必然失败。

代码实现

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        for(int i=0,j=0;i<n;){
            int g=0;
            for(j=0;j<n;j++){
                int k=(i+j)%n;
                g+=gas[k]-cost[k];
                if(g<0) break;
            }
            if(j==n) return i;
            i=i+j+1;
        }
        return -1;
    }
};