🌕🌕🌗 134. 加油站

难度: 🌕🌕🌗

问题描述

---

解法

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 思路：
        // 贪心算法，遍历数组，选取初始起点作为出发点
        // 如果该点出发满足条件，就从该点出发
        // 判断当剩余油量 <= 0 时的停止位置
        // 如果 停止位置 == 起始位置的前一点，说明正好加油一圈，满足条件
        // 如果 从起始位置开始到达不了一圈，同时，还可以得出这么一个结论
        // 假设 [x, y] 满足条件 && [x, y + 1] 不满足条件 => k ∈ [x + 1, y] 均无法满足条件，使得能到达 y + 1
        // 理由是，[x, k] 的剩余油量 必 > 0，这样都到达不了 y + 1
        // 那么从 k 出发，剩余油量可是从 0 开始的，那么更到达不了 y + 1
        int len = gas.length;
        for(int i = 0; i < len; ) {
            if(gas[i] < cost[i]) {
                i ++; // 当前起始点走不到下一个加油站，跳过
            } else {
                int preSum = gas[i] - cost[i]; // i 出发，到达下一点前剩余油量
                int j = i + 1;
                int count = 1; // 记录走过的加油站数
                while(count < len) {
                    preSum += gas[j % len] - cost[j % len]; // 走过 j 节点后，到达下一点前剩余油量
                    if(preSum < 0) {
                        // 说明还没有环绕一圈的情况下，到达不了下一个节点
                        break; // 跳出
                    }
                    count ++;
                    j ++;
                }
                if(count == len) {
                    return i; // i 出发可以走完一圈，返回结果
                } else {
                    i = j + 1; // 若 j > len 说明从 [i + 1, len] 均到达不了，在下一次 for 的循环条件中就会被卡住
                }
            }
        }
        return -1;
    }
}

---

输出