题目链接：leetcode134_加油站

暴力解法

暴力解法会尝试每个加油站作为起点，模拟一圈行驶来验证是否能成功环绕一周。这种方法的时间复杂度是 O(n^2)（超时），因为它对每个可能的起点都进行了完整的模拟。以下是暴力解法的简化描述：

1. 遍历所有加油站：将每一个加油站作为潜在的起点。
2. 模拟行驶：从当前选择的起点开始，检查是否有足够的油量到达下一个加油站，并继续此过程直到回到起点。
3. 返回结果：如果找到一个成功的起点，则返回该索引；如果所有起点都无法完成一圈，则返回 -1。

暴力解法的问题在于它没有利用已经获得的信息，每次都要重新计算，导致了不必要的重复工作。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int len = gas.size();for (int index = 0; index < len; index++){int i = index, sum = gas[i],end=0;bool flag = false;while (sum >= cost[i]){sum = sum - cost[i] + gas[(i + 1) % len];end=i+1;i = end % len;if ((end == len && index == 0) || i == 0)flag = true;if (flag && i == index)return index;}}return -1;}
};

贪心算法

初始条件

设 $x$ 和 $y$ 是两个加油站，且 $x<y$。

• $gas[i]$ 表示第 $i$ 个加油站的油量。
• $cost[i]$ 表示从第 $i$ 个加油站到下一个加油站所需的油量。

第一个不等式

$$\sum _{i=x}^{y}gas[i]<\sum _{i=x}^{y}cost[i]$$

这个不等式表明从加油站 $ x $ 到加油站 $ y $ 的总油量不足以覆盖这段路程所需的总油量，因此无法直接从 $ x $ 到达 $ y $。

第二个不等式

$$\sum _{i=x}^{j}gas[i]\ge \sum _{i=x}^{j}cost[i]\text{(对于所有 }j\in [x,y))$$

这个不等式表明对于所有位于 $ x $ 和 $ y $ 之间的加油站 $ j $，从 $ x $ 到 $ j $ 的总油量足以覆盖这段路程所需的总油量，因此可以到达这些加油站。

考虑任意加油站 $z$

现在考虑任意一个位于 $x$ 和 $y$ 之间的加油站 $z$，我们需要判断从 $z$ 出发是否能到达 $y$。

推导过程

1. 分解和

   $$\sum _{i=z}^{y}gas[i]=\sum _{i=x}^{y}gas[i]-\sum _{i=x}^{z-1}gas[i]$$

2. 应用第一个不等式

   $$\sum _{i=x}^{y}gas[i]<\sum _{i=x}^{y}cost[i]$$

   因此，

   $$\sum _{i=x}^{y}gas[i]-\sum _{i=x}^{z-1}gas[i]<\sum _{i=x}^{y}cost[i]-\sum _{i=x}^{z-1}gas[i]$$

3. 应用第二个不等式

   $$\sum _{i=x}^{z-1}gas[i]\ge \sum _{i=x}^{z-1}cost[i]$$

   因此，

   $$\sum _{i=x}^{y}cost[i]-\sum _{i=x}^{z-1}gas[i]<\sum _{i=x}^{y}cost[i]-\sum _{i=x}^{z-1}cost[i]$$

4. 简化表达式

   $$\sum _{i=x}^{y}cost[i]-\sum _{i=x}^{z-1}cost[i]=\sum _{i=z}^{y}cost[i]$$

5. 最终结论

   $$\sum _{i=z}^{y}gas[i]<\sum _{i=z}^{y}cost[i]$$

结论

从任意一个位于 $x$ 和 $y$ 之间的加油站 $z$ 出发，都无法到达加油站 $y$，因为从 $z$ 到 $y$ 的总油量不足以覆盖这段路程所需的总油量。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int totalTank = 0, currentTank = 0;int startingStation = 0;for (int i = 0; i < gas.size(); ++i) {// 更新总油量和当前油量totalTank += gas[i] - cost[i];currentTank += gas[i] - cost[i];// 如果当前油量为负，说明从起点到当前位置不可能到达，更新起点为下一个位置if (currentTank < 0) {startingStation = i + 1;currentTank = 0; // 重置当前油量}}// 如果总油量为非负数，说明可以完成一圈；否则不能完成return totalTank >= 0 ? startingStation : -1;}
};