想要精通算法和SQL的成长之路 - 加油站

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 加油站

原题链接

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

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

• 输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
• 输出: 3
• 解释:
  从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油。
  开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油。
  开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油。
  开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油。
  开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油。
  开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
  因此，3 可为起始索引。

我们先来看下暴力法怎么做。

1.1 暴力法

暴力，无非就是以每个加油站为起点，然后进行遍历，看看绕一圈之后，是否中途有断油的情况，若没有，说明这个起点是我们要的结果。

public int canCompleteCircuit(int[] gas, int[] cost) {
    for (int i = 0; i < gas.length; i++) {
        // 以当前加油站为起点，算出初始油量
        int restCapacity = gas[i] - cost[i];
        // 下一个加油站位置
        int index = (i + 1) % cost.length;
        // 开始绕一圈，要求不能断油
        while (restCapacity > 0 && index != i) {
            restCapacity += gas[index] - cost[index];
            index = (index + 1) % cost.length;
        }
        // 如果跑了一圈，回到起点，并且油有剩余就说明OK的
        if (restCapacity >= 0 && index == i) {
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

但是暴力法肯定是不行的，因为暴力法也就是穷举，这里的时间复杂度是O(N²)，因此很容易超时。因此我们需要降低时间复杂度。

1.2 贪心法

那么我们来分析一下。

• 我们假设以下标为0的加油站为起点，跑到下一个加油站。如果耗油量 > 加油量。也就是说gas[i] - cost[i]为负数。 那么以它为起点肯定是不行的了，也无需往后遍历下去。
• 那么我们就以下一个加油站（下标为1）作为起点，倘若gas[i] - cost[i]为正数。代表可以走到下标为2的加油站的。
• 那么当走到下标为3的加油站时，如果剩余油量不够了，那说明，以下标为1，为2的加油站都不能作为起点。 因为你得保证剩余油量永远 >=0。
• 如果说总加油量 < 总耗油量，那么永远不可能走完一圈。

因此我们可以这么做：

• 用一个totalRest变量，计算跑完一圈时候的剩余油量。
• 用一个curRest变量，计算当前剩余油量。startIndex作为起点下标。
• 如果curRest<0，说明之前的位置都不能作为起点，那么更新startIndex为下一个加油站。

那么最终代码就是：

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalRest = 0;// 跑完一圈剩余油量
    int curRest = 0;// 当前剩余油量
    int startIndex = 0;// 起点下标
    for (int i = 0; i < gas.length; i++) {
        totalRest += gas[i] - cost[i];
        curRest += gas[i] - cost[i];
        // 如果发生了断油，说明在[i,startIndex]这区间的加油站，都不能作为起点
        if (curRest < 0) {
            // 更新起点 和当前剩余油量
            startIndex = i + 1;
            curRest = 0;
        }
    }
    // 如果说总加油量 < 总耗油量，那么永远不可能走完一圈
    if (totalRest < 0) {
        return -1;
    }
    return startIndex;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20