LeetCode——加油站

NO.134 加油站中等

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

思路一：暴力模拟 尝试每个加油站分别作为起点出发一次。

public int canCompleteCircuit(int[] gas, int[] cost) {
    int remain = 0;
    int n = gas.length;
    //每个加油站分别作为起点
    for (int i = 0; i < n; i++) {
        //开始获得起点的所有油
        remain = gas[i];
        //j记录当前走到哪里
        int j = i;
        //当剩余油量足够到达下一站
        while (remain - cost[j] >= 0) {
            //油量-消耗+到达加油站的全部油
            remain = remain - cost[j] + gas[(j + 1) % n];
            //更新当前位置
            j = (j + 1) % n;
            //如果回到起点,则成功走了一圈
            if (j == i) {
                return i;
            }
        }
    }
    return -1;
}

时间复杂度：O(n^2)

思路二：优化暴力解法 暴力中验证每个起点时，都要将所有加油站访问一遍，大量的重复计算。

这是可以优化的，当存在可行的方案时，起点 start 将这个环形路程分成了两部分 [0 -> start] 和 [start -> i]，分别用 total 和 remain 记录这两部分剩余油量，最终的结果就是 total + remain >= 0。

让 start 从0开始、i遍历所有站点；
如果走到 i 点时油箱remain为负数，说明当前 [start -> i] 不可行，更新起点 start 为 i+1，那么之前 [start -> i] 路程计算的 remain 就成了的 [0 -> start] 的剩余油量 total；
继续从新的 start 向前走重新计算走到 i 点时油箱 remain ，如果 remain 为负数，则说明新的 [start -> i]也不可行，更新起点 start 为 i+1，那么这段新的 [start -> i] 路程计算的 remain 就需要加入 [0 -> start] 的剩余油量 total；
直至 i 遍历完毕，计算最终 start 分割出的两部分 [0 -> start] 和 [start -> i] 分别剩余油量之和 total + remain ，如果大于等于 0 说明 start 为起点可行，否则不可行。

public int canCompleteCircuit(int[] gas, int[] cost) {
    //起点
    int start = 0;
    //start为起点,[start -> i]的剩余油量
    int remain = 0;
    //0为起点,[0 -> start]的剩余油量
    int total = 0;
    for (int i = 0; i < gas.length; i++) {
        //计算当前[start -> i]的剩余油量
        remain += gas[i] - cost[i];
        //说明从当前的start出发到i,行不通
        if (remain < 0) {
            //更新起点
            start = i + 1;
            //当前[start -> i]的剩余油量,汇总进[0 -> start]的剩余油量
            total += remain;
            //重新计算新起点,[start -> i]的剩余油量
            remain = 0;
        }
    }
    //检查最终的start是否可行
    return remain + total >= 0 ? start : -1;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.134 加油站 中等

NO.134 加油站中等