时间轴

2025-10-05

init

题目：

P134 加油站

https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

非贪心算法：基于这样一个事实，如果从i到某一点j之后发现油不够了，那么i~j之间的所有点，因为假设i~j某一点k，从k出发，少了i~k的油量(从i出发能到k说明到k时油量>=0)更不可能到达j+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <vector>
using std::vector;

class Solution {
public:
  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int n = gas.size();
    // int start = -1;
    int start = 0;
    int curr_gas;
    int i, idx;
    // for (int i = 0; i < n; i++) {
    //   // 到达i前至少有多少油才能去下一个
    //   if (gas[i] - cost[i] >= 0) {
    //     start = i;
    //     break;
    //   }
    // }
    // if (start == -1) {
    //   return -1;
    // }

    while (start < n) {
      curr_gas = 0;
      i = 0;
      // 走一圈
      for (i = 0; i < n; i++) {
        idx = (start + i) % n;
        curr_gas += gas[idx] - cost[idx];
        if (curr_gas < 0) {      // 路线失败
          start = start + i + 1; // 直接跳过失败区间
          // 成功绕一圈
          break;
        }
      }
      if (i == n)
        return start;
    }

    return -1;
  }
};


标准的贪心解法：
我们是要找一个起点 start，使得从 start 出发沿环路绕一圈，油量永远 ≥ 0。

  1. 首先，同样地如果从i到某一点j之后发现油不够了，那么i~j之间的所有点，因为假设i~j某一点k，从k出发，少了i~k的油量更不可能到达j+1；
  2. 其次对于全部环路总油量total：如果 total < 0，说明整个环路油量不够，无论起点哪儿都不可能成功 → 返回 -1,如果 total >= 0，一定存在唯一一个可以成功的起点，这就是贪心方法最后返回的 start。
  3. 再者，我们从 0 遍历到 n-1 时，已经筛掉了所有不可能的起点。并且题目保证“如果存在解，则 保证 它是 唯一 的”。若最终 total >= 0，说明从最后一个 start 出发是可行的。这就说明了只需要遍历一遍是可行的。

那为什么只需遍历0~n-1就结束了呢？

形象一点来讲：当 curr_gas < 0 时我们总是把起点重置到“油量曲线最低谷”的下一个位置，所以最终的 start 是全局最低点之后的第一个站；而 total >= 0 说明从最低点之后开始，油量永远不会再跌破 0，因此能绕一整圈。

用反证法：假设最终该解法返回start,在start~n-1之间有一点k，因为结果是唯一的，如果start绕不了一圈，而是k能绕一圈，但是由于start能够到达k，所以start应该也能绕一圈，与前提存在解则唯一矛盾，因此只需遍历只需要在total>=0的情况下，存在start可以到达n-1就是所需结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <vector>
using std::vector;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int total = 0;       // 总油量差
        int curr_gas = 0;    // 当前区间油量差
        int start = 0;       // 当前起点
        int diff;

        for (int i = 0; i < n; i++) {
            diff = gas[i] - cost[i];
            total += diff;
            curr_gas += diff;

            // 如果当前区间油量为负，则不可能从 start 到 i+1
            if (curr_gas < 0) {
                // 下一站作为新的起点
                start = i + 1;
                curr_gas = 0;
            }
        }

        // 总油量小于 0，说明无解
        return (total >= 0) ? start : -1;
    }
};