134. 加油站

解法1

暴力模拟 + 缓存

走过的路，没走通。说明：中间节点也是不通的。

class Solution {
 
    boolean[] visited;
 
    private boolean canComplete(int[] gas, int[] cost, int start) {
        if (visited[start]) {
            return false;
        }
        int n = gas.length;
        int totalGas = 0;
        int now = start;
        while (true) {
            visited[now] = true;
            totalGas += gas[now];
            if (totalGas < cost[now]) {
                return false;
            }
            totalGas -= cost[now];
            now++;
            if (now == n) {
                now = 0;
            }
            if (now == start) {
                return true;
            }
        }
    }
 
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        visited = new boolean[n];
        for (int start = 0; start < n; start++) {
            if (canComplete(gas, cost, start)) {
                return start;
            }
        }
        return -1;
    }
}

解法2

走过的路，没走通。说明：中间节点也是不通的。

优化效率。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            gas[i] -= cost[i];
        }
        for (int start = 0; start < n; start++) {
            int totalGas = 0, now = start, next = start;
            while (true) {
                if (now > next) {
                    next = now;
                }
                totalGas += gas[now++];
                if (totalGas < 0) {
                    break;
                }
                if (now == n) {
                    now = 0;
                }
                if (now == start) {
                    return now;
                }
            }
            start = next;
        }
        return -1;
    }
}