Zoe Ding's Blog

134. Gas Station

134. Gas Station

Sol 1

Brute Force. Time = O(n^2)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int startIndex = 0; startIndex < gas.length; startIndex++) {
            if (canTravel(gas, cost, gas.length, startIndex)) {
                return startIndex;
            }
        }
        return -1;
    }
    
    private boolean canTravel(int[] gas, int[] cost, int nums, int startIndex) {
        int index = startIndex;
        int curGas = 0;
        while (index < nums) {
            curGas += gas[index] - cost[index];
            if (curGas < 0) {
                return false;
            }
            index ++;
        }
        index = 0;
        while (index < startIndex) {
            curGas  += gas[index] - cost[index];
            if (curGas < 0) {
                return false;
            }                
            index ++;
        }
        return true;
    }
}

Sol 2

思想：link

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int nums = gas.length;
        int curTank = 0;
        int totalTank = 0;
        int startingStation = 0;
        for (int i = 0; i < nums; i++) {
            curTank += gas[i] - cost[i];
            totalTank += gas[i] - cost[i];
            if (curTank < 0) {
                curTank = 0;
                startingStation = i + 1;
            }
        }
        return totalTank >= 0 ? startingStation : -1;
    }
}