Accept answer of gas station


  • 0
    L
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        if(n<=0) return -1;
        
        int[] delta = new int[n];
        for(int i=0;i<n;i++)
            delta[i] = gas[i]-cost[i];
            
        int[] G = new int[n];
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<n;i++)
        {
            sum+=delta[i];
            if(sum<min)
                min = sum;
        }
        G[0] = min;
        if(G[0]>=0)
            return 0;
        for(int i=1;i<n;i++)
        {
            G[i] = (G[i-1]-delta[i-1] < sum)?(G[i-1]-delta[i-1]):sum;
            if(G[i]>=0) return i;
        }
        return -1;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.