加油站
文章目录
- 加油站
- 1 题目描述
- 2 思路
- 3 解题方法
1 题目描述
https://leetcode.cn/problems/gas-station/
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
2 思路
正如大部分大佬所言，需要找到最小值所在的点。但是他们的代码写得有些含糊，我希望可以使用一种更加符合直觉的方式。
我们假设从i号加油站出发，然后用一张折线图表示到达每个加油站（最终返回i）时的剩余油量。x轴为加油站号，y轴为剩余油量。一开始的时候，剩余油量为0。首先来看一种可能的情况：
gas = [4, 3, 1, 2, 7, 4]
cost = [1, 2, 7, 3, 2, 5]
这里我们提供代码来表示从不同的站点出发，到达不同站点时候的剩余油量：
gas = [4,3,1,2,7,4]
cost = [1,2,7,3,2,5]
# 绘制
fig, axs = plt.subplots(1, 6, figsize=(20, 3))
for s in range(len(gas)):
left_gas = [0 for _ in range(len(gas))]
for i in range(len(gas)):
left_gas[i] = (left_gas[i-1] if i > 0 else 0) + gas[(s + i) % len(gas)] - cost[(s + i) % len(gas)]
left_gas.insert(0, 0)
x = [(s + i) % len(gas) for i in range(len(gas))]
x.append(s)
axs[s].plot(range(len(gas) + 1), left_gas)
axs[s].scatter(range(len(gas) + 1), left_gas)
# 设置 x 轴刻度及标签
axs[s].set_xticks(np.arange(len(gas) + 1))
axs[s].set_xticklabels(x)
# 绘制0刻度线
axs[s].axhline(y=0, color='r', linestyle='-')
# 将最低点标记出来，最低点的索引为left_gas.index(min(left_gas))
axs[s].scatter(left_gas.index(min(left_gas)), min(left_gas), color='r')
plt.show()
你可以明显地看到从哪里出发，可以安全地开一圈了。（红线为0刻度线，红色点为最小点）
那么我们再举一个不可能开一圈的例子：
gas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 0~9号加油站的油量
cost = [10, 9, 8, 7, 6, 5, 4, 3, 2, 11] # 0~9号加油站到下一站的消耗
其对应图像为
我这里也提供对应的绘图代码：
import matplotlib.pyplot as plt
import numpy as np
gas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 0~9号加油站的油量
cost = [10, 9, 8, 7, 6, 5, 4, 3, 2, 11] # 0~9号加油站到下一站的消耗
# 绘制
# fig, axs = plt.subplots(1, 10, figsize=(20, 3))
# 上下两行，每行5个子图
fig, axs = plt.subplots(2, 5, figsize=(20, 6))
for s in range(len(gas)):
left_gas = [0 for _ in range(len(gas))]
for i in range(len(gas)):
left_gas[i] = (left_gas[i - 1] if i > 0 else 0) + gas[(s + i) % len(gas)] - cost[(s + i) % len(gas)]
left_gas.insert(0, 0)
x = [(s + i) % len(gas) for i in range(len(gas))]
x.append(s)
# 设置 x 轴刻度及标签
axs[int(s / 5)][s % 5].set_xticks(np.arange(len(gas) + 1))
axs[int(s / 5)][s % 5].set_xticklabels(x)
axs[int(s / 5)][s % 5].plot(range(len(gas) + 1), left_gas)
axs[int(s / 5)][s % 5].scatter(range(len(gas) + 1), left_gas)
# 绘制0刻度线
axs[int(s / 5)][s % 5].axhline(y=0, color='r', linestyle='-')
# 将最低点标记出来，最低点的索引为left_gas.index(min(left_gas))
axs[int(s / 5)][s % 5].scatter(left_gas.index(min(left_gas)), min(left_gas), color='r')
# 最低点设置垂直虚线，只往下画
axs[int(s / 5)][s % 5].axvline(x=left_gas.index(min(left_gas)), color='r', linestyle='--')
plt.show()
什么情况下能转完一圈？ 即总油量大于等于总耗油量。
3 解题方法
其实就是根据直觉，创建一个长度为gas.length + 1（参考上面的图，走一圈回来，相当于一共gas.length+1个站点）的数组left_gas（剩余油量），i位置初始为0，表示为在站点i出发时，剩余油量（或者说，初始油量）为0。
每两个站点之间的增加或者减少量是一定的，即任何两点之间连线的斜率是不变的（gas[i] - cost[i]），只要我们让最低值大于等于0，就可以保证走一圈。怎么让最低值大于等于0？只要我们让最低值为出发点，不就能保证其为0了？也就是能够保证最低点大于等于0。
所以，我们只需要找到最低点即可。
我们设置小车从0号站点出发，然后我们计算每个站点的剩余油量：
class Solution(object):
def canCompleteCircuit(self, gas, cost):
res = [0 for _ in range(len(gas) + 1)] # 剩余油量，为什么是len(gas) + 1，参考图中的x轴
min_index = 0 # 初始站点
min_left = 0 # 初始油量
for i in range(len(gas)):
res[i + 1] = res[i] + gas[i] - cost[i] # 例如，站点1的时候，剩余油量=res[0] + gas[0] - cost[0]
if res[i + 1] < min_left: # 记录最低点的值和索引
min_left = res[i + 1]
min_index = i + 1
return -1 if res[-1] < 0 else min_index # 到达最最终点的时候，相当于所有的gas相加，然后减去所有的cost，
# 如果返回开头的时候，剩余油量小于0，则返回-1
相比之下，leetcode很多大佬的代码让我有点迷茫（没有说大佬写得不好，只是我有点难理解）：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0 ;
int min_num = Integer.MAX_VALUE;
int min_index = 0;
for ( int i = 0 ; i < gas.length ; i ++){
sum += gas[i] - cost[i];
if(sum<=min_num && gas[(i+1)%gas.length] >0){
min_index = i;
min_num = sum;
}
}
return sum < 0 ? -1 : (min_index +1 ) % gas.length;
}
}
