day-24 加油站

参考了答案。。。。。。

思路：借用用户Tristan的一段话：
首先判断总gas能不能大于等于总cost，如果总gas不够，一切都白搭对吧（总（gas- cost）不用单独去计算，和找最低点时一起计算即可，只遍历一次）；
再就是找总（gas-cost）的最低点，不管正负（当然如果最低点都是正的话那肯定能跑完了）此时返回零；
找到最低点后，如果有解，那么解就是最低点的下一个点，因为总（gas-cost）是大于等于0的，所以前面损失的gas我从最低点下一个点开始都会拿回来！，别管后面的趋势是先加后减还是先减后加，最终结果我是能填平前面的坑的。

code:

class Solution {

    public int canCompleteCircuit(int[] gas, int[] cost) {

        int length = gas.length;
        int rest = 0;
        int minRest = Integer.MAX_VALUE;
        int minIndex = 0;

        for (int i = 0; i < length; i++) {

            rest += gas[i] - cost[i];//到达下一加油站剩余油量
            if (rest < minRest) {

                minRest = rest;
                minIndex = i;
            }
        }
        if (rest < 0) return -1;//无解
        else if (minRest >= 0) return 0;//任何点开始都能绕一圈
        else return (minIndex + 1) % length;//有解 解就是最低点的下一个点
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/136833155

目录