Leetcode 134. 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, otherwise return -1.

Note:
The solution is guaranteed to be unique.

题意：一个环路上有n个加油站，gas[i]代表加油站i能加多少油，cost[i]代表从i到i+1耗费多少油，问是否能找到一个加油站i，保证从它开始行驶能走完一圈。

思路：
开始的思路是用深度搜索的方法，尝试从每个加油站走，看是否能走完一圈。

public int canCompleteCircuit(int[] gas, int[] cost) {
    if (gas == null || gas.length < 2) {
        return 0;
    }

    int len = gas.length;
    int[] circle = new int[2*len];
    for (int i = 0; i < circle.length; i++) {
        circle[i] = gas[i % len];
    }

    for (int i = 0; i < len; i++) {
        if (helper(circle, cost, 0, 0, 0)) {
            return i;
        }
    }

    return -1;
}

private boolean helper(int[] circle, int[] cost, int pos, int num, int gas) {
    if (num == cost.length) {
        return true;
    }

    gas += circle[pos] - cost[pos % cost.length];
    if (gas < 0) {
        return false;
    }

    return helper(circle, cost, pos + 1, num + 1, gas);
}

Leetcode超时，查看相关解法，发现是用贪心法，核心点是如果从i最远行驶到k，那么i到k中任何一个加油站都无法走完一圈。并且如果全部加油站的和小于耗费油的和也是无法走完一圈的。所以如果最后加油的和大于耗费的和，返回最后一个满足条件的起始位置。

public int canCompleteCircuit1(int[] gas, int[] cost) {
if (gas == null || gas.length == 0 || gas.length != cost.length) {
return -1;
}

    int start = 0, sum = 0, total = 0;
    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
        sum += gas[i] - cost[i];
        if (sum < 0) {
            start = i + 1;
            sum = 0;
        }
    }

    return total < 0 ? -1 : start;
}