134.gas-station 加油站

问题描述

134.加油站

解题思路

考虑两个变量，一个是总油耗total_oil，一个是从起点到下一个站点后汽车内部剩余的汽油cur_oil(没有在目标站点补充油耗)。
总油耗total_oil < 0，说明不可能到;
cur_oil < 0，则以到达的站点作为新的起点再出发;

代码

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        int total_tank = 0;
        int curr_tank = 0;
        int starting_station = 0;
        for (int i = 0; i < n; ++i) {
            //总和必须大于等于0，否则不能完成绕行
            total_oil += gas[i] - cost[i];
            cur_oil += gas[i] - cost[i];
            if (curr_tank < 0) {
                // 一个站的收益如果小于0，肯定不能作为起点；而连续的多个站也可以等效地看做一个站，如果其累积收益小于0，就跳过，寻找下一个。
                starting_station = i + 1;
                // 还原到初始状态
                cur_oil = 0;
            }
        }
        return total_oil >= 0 ? starting_station : -1;
    }
}