LeetCode刷题实战134：加油站-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 加油站，我们先来看题面：

https://leetcode-cn.com/problems/gas-station/

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.

题意

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。

输入数组均为非空数组，且长度相同。

输入数组中的元素均为非负数。

样例

输入: 
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

解题

https://segmentfault.com/a/1190000003817799

我们把将gas中每个值都减去cost中对应的值，这样gas就成为了开出该加油站到下一个加油站时，该加油站加的油用剩到多少。这样我们用一个tank变量记录汽车每开到一个加油站后油箱里累计剩下多少油，每到一个加油站就更新。这样我们开始遍历gas数组，如果tank是负数，说明开出该加油站后无法到达下一个加油站，这样旅程的起点更新为下一个加油站。因为旅程是环状的我们遍历的加油站数组应为2*gas.length-1，这样能保证我们以最后一个加油站为起点时也能继续验证。

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // gas减去cost，得到净油值
        for(int i = 0; i < cost.length; i++){
            gas[i] -= cost[i];
        }
        int tank = 0, res = -1;
        for(int i = 0; i < gas.length * 2 - 1; i++){
            int idx = i % gas.length;
            // 更新油箱
            tank += gas[idx];
            // 如果油箱为负，说明走不到下一个加油站
            if(tank < 0){
                res = idx + 1;
                tank = 0;
            }
        }
        // 如果起点在最后一个加油站之后，说明无解
        return res >= gas.length ? -1 : res;
    }
}