文章目录
- 134. 加油站
- 题目描述
- 暴力枚举（超时）
- 代码一
- 代码二（优化）
- 贪心算法
- 方法一
- 方法二
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]
输出: 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 可为起始索引。
示例 2:
输入: 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 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
提示:
- gas.length == n
- cost.length == n
- 1 <= n <= 105
- 0 <= gas[i], cost[i] <= 104
暴力枚举（超时）
暴力的方法很明显就是O(n^2)的，遍历每一个加油站为起点的情况，模拟一圈。
如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。
暴力的方法思路比较简单，但代码写起来也不是很容易，关键是要模拟跑一圈的过程。
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
代码一
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
// 遍历每个加油站作为起点
for(int i = 0; i < gas.size(); i++) {
// 如果当前加油站的汽油不足以到达下一个加油站，则跳过
if(gas[i] < cost[i])
continue;
else {
// sum用于存储从当前加油站出发，行驶过程中的油量净增加值
int sum = gas[i] - cost[i];
// 计算下一个加油站的索引
int n = (i + 1) % gas.size();
// 如果下一个加油站就是当前加油站，意味着只有一个加油站，直接返回当前加油站的索引
if(n == i)
return i;
// 否则，继续尝试从当前加油站出发，尝试绕一圈回到起点
while(n != i) {
// 累加从当前加油站到下一个加油站的油量净增加值
sum += gas[n] - cost[n];
// 如果中途油量不足以到达下一个加油站，跳出循环
if(sum < 0)
break;
else {
// 计算起点加油站的前一个加油站索引
int z = i - 1;
if(i - 1 < 0)
z = gas.size() - 1;
// 如果下一个加油站是起点加油站的前一个加油站，意味着已经成功绕一圈，返回当前加油站索引
if(n == z)
return i;
}
// 更新下一个加油站的索引
n++;
n = n % gas.size();
}
}
}
// 如果遍历完所有加油站都无法找到能绕一圈回到起点的加油站，返回-1
return -1;
}
};
代码二（优化）
这段代码是针对“加油站”问题的一个解决方案。该问题要求在一条环形路线上找到一个加油站，从该站出发，汽车能够绕环形路线行驶一周并回到起点。下面是对该解决方案的详细注释说明：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
// 遍历每一个加油站作为可能的起点
for(int i=0; i<gas.size(); i++) {
// 初始化sum为从当前加油站出发的油量与消耗的差值
int sum = gas[i] - cost[i];
// 计算下一个加油站的索引。因为是环形，所以使用取余操作
int index = (i + 1) % gas.size();
// 当当前的油量剩余大于0，并且还没有回到起点加油站时，继续行驶
while(sum > 0 && index != i) {
// 更新sum，加上在当前加油站加的油，并减去到下一站的消耗
sum += gas[index] - cost[index];
// 更新下一个加油站的索引，仍然使用取余操作保证环形属性
index = (index + 1) % gas.size();
}
// 如果最后的油量sum不小于0，并且已经回到了起点，这表明找到了一个可行的起点
if(sum >= 0 && index == i) return i;
}
// 如果遍历完所有加油站都没有找到可行的起点，返回-1
return -1;
}
};
解题思路简述：
-
尝试每一个加油站作为起点： 由于不知道哪个加油站能够使汽车成功绕环形路线一周，代码首先尝试将每一个加油站设为起点。
-
计算油量差值： 对于每一个尝试作为起点的加油站，计算从该站出发至下一站的油量剩余（即当前加油站的油量减去到下一站的油耗）。
-
环形行驶检查： 从尝试的起始加油站开始，根据油量差值判断是否能够继续前往下一个加油站。这一过程一直持续到汽车要么无法继续前进（油量差值变为负），要么回到了起点。
-
判断成功条件： 如果最终汽车油量不小于0并且回到了起点，意味着从当前尝试的起点出发可以成功绕环形路线一周。返回这个加油站的索引。
-
全部尝试失败： 如果所有加油站作为起点都无法满足条件，则返回-1，表示无法完成这样的环形旅行。
这段代码通过尝试每个加油站作为起点，并检查是否可以环绕一周，来解决问题。虽然有效，但是效率较低，因为它对于每一个起点都从头开始计算。优化方法包括使用“贪心算法”来减少不必要的重复计算，这种方法可以显著提高算法的效率。
贪心算法
方法一
直接从全局进行贪心选择，情况如下：
情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。
C++代码如下：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
// curSum 用来记录从起点出发的总油量净增加值
int curSum = 0;
// min 用来追踪从起点开始，油箱中油量的最小值
int min = INT_MAX; // 初始化为最大整数，以便于后续的比较
// 遍历所有加油站，计算从起点出发的总油量净增加值，并找出最小油量值
for (int i = 0; i < gas.size(); i++) {
// rest 是当前加油站的油量与消耗油量的差值
int rest = gas[i] - cost[i];
// curSum 累加所有油站的油量净增加值
curSum += rest;
// 更新最小油量值
if (curSum < min) {
min = curSum;
}
}
// 情况1: 如果最终油量净增加值小于0, 说明无法绕环路行驶一周
if (curSum < 0) return -1;
// 情况2: 如果从起点出发的油量最小值大于或等于0, 则起点为0的位置可以行驶一周
if (min >= 0) return 0;
// 情况3: 如果上述情况都不满足，需要从后向前遍历，找到新的出发点
for (int i = gas.size() - 1; i >= 0; i--) {
// 计算从当前加油站出发的油量净增加值
int rest = gas[i] - cost[i];
// 从后向前累加油量净增加值，并更新最小油量值
min += rest;
// 一旦最小油量值大于等于0, 则当前加油站的位置可以作为出发点
if (min >= 0) {
return i; // 返回该加油站作为新的出发点
}
}
// 如果没有合适的出发点，返回-1
return -1;
}
};
代码分析了三种情况：
-
情况1：如果在遍历所有加油站之后，总油量净增加值(
curSum)小于0，则说明油量不足以绕环路行驶一周，此时应该返回-1。 -
情况2：如果从起点到任何加油站的过程中，油箱中油量的最小值(
min)大于或等于0，则说明可以从0位置开始，顺利绕环路行驶一周，此时应该返回0。 -
情况3：如果上述两种情况都不满足，即总油量是足够的，但是油箱中油量的最小值(
min)小于0，则需要从后向前遍历加油站。这是因为如果存在一个解，那么油箱中油量最小值(min)之后的加油站即为新的出发点。在这个循环中，我们通过从后向前累加油量差值来更新min，一旦min非负，就找到了新的出发点。
这个算法的关键在于利用了油量净增加的累加和与最小值来决定出发点。如果全程油量净增加为负，那么无论如何都无法完成环路行驶。如果全程油量净增加为正，那么必定存在一个加油站，它的下一个加油站是可以作为出发点的，因为从这一点开始油量将始终为正直到行驶结束。
其实我不认为这种方式是贪心算法，因为没有找出局部最优，而是直接从全局最优的角度上思考问题。
但这种解法又说不出是什么方法，这就是一个从全局角度选取最优解的模拟操作。
所以对于本解法是贪心，我持保留意见！
但不管怎么说，解法毕竟还是巧妙的，不用过于执着于其名字称呼。
方法二
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
如图：
那么为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。
那有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？ 如图：
如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。
区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择其实位置了。
那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。
局部最优可以推出全局最优，找不出反例，试试贪心！
C++代码如下：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
// 定义sum来记录全程的油量差（加油量-消耗量），用以判断整个环形路线是否能够走完
int sum=0;
// 定义cur来记录当前油量差，用以判断从某个加油站出发是否能到达下一个加油站
int cur=0;
// 定义start来记录起始加油站的位置，默认为0，即第一个加油站
int start=0;
// 遍历所有加油站
for(int i=0;i<gas.size();i++)
{
// 更新当前油量差，表示从这个加油站出发到达下一个加油站后的油量变化
cur+=gas[i]-cost[i];
// 同时更新全程油量差
sum+=gas[i]-cost[i];
// 如果当前油量差小于0，意味着无法从当前加油站到达下一个加油站
if(cur<0)
{
// 重置当前油量差，从下一个加油站重新开始计算
cur=0;
// 将下一个加油站设为新的起点
start=i+1;
}
}
// 如果全程油量差小于0，意味着无论从哪个加油站出发，都无法完成全程行驶，返回-1
if(sum<0) return -1;
// 如果全程油量差不小于0，返回能够作为起点的加油站位置
return start;
}
};
这个解决方案的核心思想是使用贪心算法的策略，通过一次遍历来确定能否绕环路行驶一周，以及从哪个加油站出发。
-
全程油量差(
sum)： 确定整个环路是否能走完。如果sum最终小于0，意味着加油量总和小于消耗量总和，因此不可能完成环路行驶。 -
当前油量差(
cur)： 用来判断从当前起点出发，能否顺利到达下一个加油站。如果cur在任何时点小于0，说明从当前起点无法走完全程，需要将下一个加油站设为新的起点，并重新计算。 -
起始加油站(
start)： 记录在满足条件下，可以作为行驶全程起点的加油站位置。
通过这种方式，代码在遍历一次所有加油站的过程中，有效地判断出了是否存在可行解，以及可行解的具体位置。
