根据题解
这道题使用贪心算法,找到当前可解决问题的状态即可
「贪心算法」的问题需要满足的条件:
- 最优子结构:规模较大的问题的解由规模较小的子问题的解组成,规模较大的问题的解只由其中一个规模较小的子问题的解决定;
- 无后效性:后面阶段的求解不会修改前面阶段已经计算好的结果;
- 贪心选择性质:从局部最优解可以得到全局最优解。
如果要求走一圈,则总剩余油量total
应该大于等于0
而在每个站点的时候,当前剩余油量curr
如果大于等于0,代表可以到达下一个站点,如果小于0,代表从当前及之前的站点出发无法到达下一个站点,于是出发点改为下一个站点。
为什么说当前及之前的站点出发都无法到达下一个站点呢?
参考这个题解的图:
可以看到,假设start
已经更改为3之后,可以到达4,假设到下一个节点时,cursum
变成了负数,而在这之前的两个站点的cursum
都是正数,代表它俩的加和都不够,更别提其中一个了 ,所以start
会跳过4,更新为i+1
。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int start = 0;
int curr = 0;
int total = 0;
for (int i = 0; i < n; ++i) {
curr += gas[i] - cost[i];
total += gas[i] - cost[i];
if (curr < 0) {
start = i + 1;
curr = 0;
}
}
return total >= 0 ? start : -1;
}
};