leetcode：134. 加油站

题目

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例：

  1. 输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
  2. 输出: 3
  3. 解释:
  4. 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
  5. 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
  6. 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
  7. 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
  8. 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
  9. 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
  10. 因此，3 可为起始索引。
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

解答 & 代码

解法 0：二重循环暴力模拟（超时）

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int len = gas.size();
        // 遍历每个起点
        for(int start = 0; start < len; ++start)
        {
            // 如果当前起点的油 > 到下个加油站的消耗，则可以从当前节点出发
            if(gas[start] >= cost[start])
            {
                int curGas = 0;
                bool ableDrive = true;
                // 遍历一圈，看能否绕一周
                for(int step = 0; step < len; ++step)
                {
                    int idx = (start + step) % len;
                    curGas += gas[idx] - cost[idx];
                    // 若无法开到下个加油站，则不能以 start 作为起点绕一周
                    if(curGas < 0)
                     {
                        ableDrive = false;
                        break;
                     }
                }
                // 如果能以 start 为起点绕一周，则直接返回 start
                if(ableDrive == true)
                    return start;
            }
        }
        // 遍历完所有起点都无法绕一周，则返回 -1
        return -1;
    }
};

复杂度分析：设加油站个数为 N

  • 时间复杂度[中等] 134. 加油站 - 图1：
  • 空间复杂度 O(1)：

解法 1：贪心

贪心思想：从起点 start 出发，如果卡在 end 点，无法从 end 到下一个加油站，那么从 [start, end] 区间内的任意位置 i 出发，都无法到达 end 到下一个加油站。因为如果从位置 i 出发能到达 end 到下一个加油站，而位置 i 又可以从位置 start 出发到达，那么按理说从 start 就能到达 end 到下一个加油站，这就矛盾了。因此直接跳到 end 的下一个加油站，作为新的 start，判断能否环绕一周

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int len = gas.size();
        int start = 0;
        while(start < len)
        {
            // 如果当前起点能出发（即起点加油站的油 > 到下一个加油站的油耗）
            // 则判断能否从当前起点出发环绕一周
            if(gas[start] >= cost[start])
            {
                int curGas = 0;
                int step = 0;
                for(; step < len; ++step)
                {
                    int idx = (start + step) % len;
                    curGas += gas[idx] - cost[idx];
                    if(curGas < 0)
                        break;
                }
                // 如果可以环绕一周，则直接返回起点 start
                if(step == len)
                    return start;
                // 如果不能环绕一周，卡在 end = start + step 的位置不能到下一个加油站
                // 则从 [start, end] 的任意位置都无法到达 end 的下一个加油站（贪心）
                // 因此起点直接跳到 end 后一位
                else
                    start = start + step + 1;
            }
            else
                ++start;
        }
        return -1;
    }
};

复杂度分析：设加油站个数为 N

  • 时间复杂度 O(N)：对数组进行了单次遍历
  • 空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：84 ms, 在所有 C++ 提交中击败了 19.91% 的用户
内存消耗：67.7 MB, 在所有 C++ 提交中击败了 61.65% 的用户