这题的证明挺有意思的，可以看一下官方题解。
从某一个车站出发，只要到最后一个车站的油够用，并且全程的油耗加起来大于等于0，那么从该车站出发就能走一圈。
C++代码：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int res = 0;
int sum = 0;
int cur_tank = 0;
for(int i = 0; i < gas.size(); i++){
sum += (gas[i] - cost[i]);
cur_tank += (gas[i] - cost[i]);
if(cur_tank < 0){
cur_tank = 0;
res = i + 1;
}
}
if(sum < 0 || res == gas.size()) return -1;
return res;
}
};
LeetCode-134-加油站 134. 加油站[https://leetcode-cn.com/problem...
134.加油站 https://leetcode-cn.com/problems/gas-station/[htt...
题目描述 这是 LeetCode 上的 「134. 加油站」 ，难度为 「中等」。 在一条环路上有N个加油站，其中...
这题的证明挺有意思的，可以看一下官方题解。 从某一个车站出发，只要到最后一个车站的油够用，并且全程的油耗加起来大于...
134. 加油站[https://link.zhihu.com/?target=https%3A//leetcod...
题目描述（中等难度） 把这个题理解成下边的图就可以。 每个节点表示添加的油量，每条边表示消耗的油量。题目的意思就是...
134. 加油站 在一条环路上有N个加油站，其中第i个加油站有汽油gas[i]升。 你有一辆油箱容量无限的的汽车，...
解题思路 1.计算每一站到下一站的盈余油量2.如果如果总盈余量小于0，从任何节点起步都不足以跑一圈如果总盈余量大于...
984. 不含 AAA 或 BBB 的字符串 相关标签 ： 贪心算法 134. 加油站 相关标签： 贪心算法
在一条环路上有N个加油站，其中第i个加油站有汽油gas[i]升。 你有一辆油箱容量无限的的汽车，从第i个加油站开往...
本文标题：LeetCode 134. 加油站
本文链接：https://www.haomeiwen.com/subject/umlgpktx.html
网友评论