博文中会简要介绍Leetcode P0134题目分析及解题思路。

“Gas Station”这道题是一道非常经典的贪心算法的问题。这道题利用贪心算法可以在O(n)的时间复杂度内得到结果。

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.

这道题的核心思路在于思考如何确定起点。这道题的实际要求是从起点出发，剩余油量必须恒大于等于零。我们以这个需求为抓手，来设计贪心算法的思路。

我们从station i出发（i可以是任意合法下标），若这个station的预期剩余油量是负数，即供油量减去耗油量，那么若我们当前的剩余油量，即下述tank中的油量，足够用，则扣除tank中的相应的油量，若不够用则扣光tank中的油量（这里就是贪心算法的第一个核心，不断将使用当前剩余的可用油量直到用光），并且不足的部分添加到required里，这里的required指的是未来的油量刚需。

若这个station的预期剩余油量是正数，那么如果没有记录起点，则将当前坐标作为起点，然后将剩余油量添加到tank中（这里就是贪心算法的第二个核心，不断将扩大可用油量以满足后续开销）。最后用tank中的油量扣除未来的油量刚需required，若大于等于零，则可达，反之则无法绕一圈。

以下是Java的题解代码实现。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int tank = 0, required = 0, start = -1, N = gas.length;
        for (int idx=0; idx<N; ++idx) {
            int saved = gas[idx]-cost[idx];
            if (saved < 0) {
                if (tank == 0)
                    required += saved;
                else {
                    if (tank+saved >= 0)
                        tank += saved;
                    else {
                        required += (saved+tank);
                        tank = 0;
                        start = -1;
                    }
                }
            }
            else {
                if (start == -1)
                    start = idx;
                
                tank += saved;
            }
        }
        
        return (tank+required >= 0)? start: -1;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tank = 0, required = 0, start = -1, N = gas.size();
        for (int idx=0; idx<N; ++idx) {
            int saved = gas[idx]-cost[idx];
            if (saved < 0) {
                if (tank == 0)
                    required += saved;
                else {
                    if (tank+saved >= 0)
                        tank += saved;
                    else {
                        required += (tank+saved);
                        tank = 0;
                        start = -1;
                    }
                }
            }
            else {
                if (start == -1)
                    start = idx;
                
                tank += saved;
            }
        }
        
        return (tank+required >= 0)? start: -1;
    }
};