加油站

题目链接

55.跳跃游戏

解题思路

如果从 start 出发到 i 时油量已经小于 0，说明 start ~ i 中任何一个位置都不能作为起点，所以下一个可能起点只能是 i + 1。

代码实现

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;   // 总油量盈亏
        int cur = 0;     // 当前从 start 出发的油量盈亏
        int start = 0;   // 起点

        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];

            total += diff;
            cur += diff;

            if (cur < 0) {
                start = i + 1;
                cur = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
}

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(1)$