LeetCode: 134. Gas Station

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

134. Gas Station

LeetCode - 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.

Example 1:

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

Output: 3

*Explanation:
*Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input:
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

*Explanation:
*You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Gas Station.
 *
 * Memory Usage: 39.1 MB, less than 5.88% of Java online submissions for Gas Station.
 *
 * Copy from: https://leetcode-cn.com/problems/gas-station/solution/jia-you-zhan-by-leetcode/[加油站 - 加油站 - 力扣（LeetCode）]
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-25 21:55
 */
public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    int totalTank = 0;
    int currentTank = 0;
    int startStation = 0;
    for (int i = 0; i < n; i++) {
        totalTank += gas[i] - cost[i];
        currentTank += gas[i] - cost[i];
        if (currentTank < 0) {
            startStation = i + 1;
            currentTank = 0;
        }
    }
    return totalTank >= 0 ? startStation : -1;
}