Leetcode 134 加油站

题意理解：

????????给定n个站点，两个数组gas表达每个站点可加的油量，cost表达到下一站点所需耗费的油量。

????????gas = [1,2,3,4,5], cost = [3,4,5,1,2]

????????要求从下表为i的站点开始，刚好能支撑汽车在每个站点转一圈后回到出发位置。

????????

解题思路：

? ? ? ? 当前站剩余油量累计-下一站耗油<0，行程被迫中止，前几站到到该站剩余的油量不足以支撑这几站的油量耗费，我们需要选择新的起始位置。

? ? ? ? 此时我们选择当前站的下一站作为起始站，重新开始。

注意：

????????我们总是重复此过程。则不会出现到此处行程截止，但中间存在可完成行程的开始节点。

????????

? ? ? ? 假设：

????????????????位置2处截止,开往下一节点剩余油<0，但是存在位置1处开始到位置2，开往下一节点后剩余油>0,

????????那么：

????????????????必然存在位置0->位置1,从位置1开往下一节点剩余油<0,

????????因为：

????????????????我们总是在开往下一节点剩余油<0时，更换起始节点

????????故：

????????????????从位置0-位置2，不存在一个可开始的位置1，使位置1到位置2，开往下一节点剩余油>0。

? ? ? ? 所以：

? ? ? ? ? ? ? ? 当开往下一节点剩余油<0时，将当前节点的下一个节点作为起始节点是合理的。? ?

? ? ? ? 其次：

????????????????若所有站点油和<所有路程耗费，则说明任何一个节点开始都无法完成形成，返回下标-1.

1.贪心解题

public int canCompleteCircuit(int[] gas, int[] cost) {
        int start=0;
        int curGos=0;
        int totalGos=0;
        for(int i=0;i< gas.length;i++){
            //当起始位置到此处时，开往下一节点剩余油<0,行程截止
            if(curGos<0){
                //更换起始位置，重新开始计算
                curGos=0;
                start=i;
            }
            curGos+=(gas[i]-cost[i]);
            totalGos+=(gas[i]-cost[i]);//记录所有行程耗油剩余量
        }
        //若所有节点耗油剩余量<0,则从任何节点开始都走不完行程。
        if(totalGos<0) return -1;
        return  start;
    }

2.分析

时间复杂度：O(n)

空间复杂度：O(1)

n表示输入数组的大小