134. 加油站

题意：

解题思路：

思路：
1. 暴力解法O(n2)：枚举每一个加油站作为起点，判断该起点的油能否到下一个加油站，如果不能则跳到下一个加油站作为起点，出发，直到环绕一周。
2. (优化) O(n)：暂定i~j加油站能成功，但是i不能到达j+1加油站，则i~j中的所有加油站必然都不能到达j+1加油站，所以可以直接跳过j，从下一个j+1加油站作为起点，继续向下一个出发；

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $gas
     * @param Integer[] $cost
     * @return Integer
     */
    //暴力
    function canCompleteCircuit($gas, $cost) {
        $n = count($gas);
        for ($i = 0; $i < $n; $i++) {
            $tank = 0;
            for ($j = $i; $j < $i + $n; $j++) {
                $k = $j % $n;
                $tank += $gas[$k] - $cost[$k];
                if ($tank < 0) break;
            }
            if ($tank >= 0) return $i;
        }
        return -1;
    }
     //暴力优化
    function canCompleteCircuitSkip($gas, $cost) {
        $n = count($gas);
        $j = 0;
        for ($i = 0; $i < $n; $i = $j + 1) {
            $tank = 0;
            for ($j = $i; $j < $i + $n; $j++) {
                $k = $j % $n;
                $tank += $gas[$k] - $cost[$k];
                if ($tank < 0) break;
            }
            if ($tank >= 0) return $i;
        }
        return -1;
    }
    //贪心算法
    function canCompleteCircuitGreedy($gas, $cost) {
        $total = 0;
        $sum = 0;
        $start = 0;
        for ($i = 0; $i < count($gas); $i++) {
            $total += $gas[$i] - $cost[$i];
            $sum += $gas[$i] - $cost[$i];
           // echo $total.'&&&&&'.$sum;echo PHP_EOL;
            if ($sum < 0) {
                $start = $i + 1;
                $sum = 0;
            }
        }
        return ($total < 0) ? -1 : $start;
    }
}

GO代码实现：

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)
    for i := 0; i < n; i++ {
        tank := 0
        for j := i; j < i + n; j++ {
            k := j % n
            tank += gas[k] - cost[k]
            if tank < 0 {
                break
            }
        }
        if tank >= 0 {
            return i
        }
    }
    return -1
}