首页 > 代码库 > Leetcode# 134 Gas station
Leetcode# 134 Gas station
原题地址
非常经典的一道题。可以转换成求最大连续和做，但是有更简单的方法。基于一个数学定理：
如果一个数组的总和非负，那么一定可以找到一个起始位置，从他开始绕数组一圈，累加和一直都是非负的
（证明貌似不难，以后有时间再补）
有了这个定理，判断到底是否存在这样的解非常容易，只需要把全部的油耗情况计算出来看看是否大于等于0即可。
那么如何求开始位置在哪？
注意到这样一个现象：
1. 假如从位置i开始，i+1，i+2...，一路开过来一路油箱都没有空。说明什么？说明从i到i+1，i+2，...肯定是正积累。
2. 现在突然发现开往位置j时油箱空了。这说明什么？说明从位置i开始没法走完全程(废话)。那么，我们要从位置i+1开始重新尝试吗？不需要！为什么？因为前面已经知道，位置i肯定是正积累，那么，如果从位置i+1开始走更加没法走完全程了，因为没有位置i的正积累了。同理，也不用从i+2，i+3，...开始尝试。所以我们可以放心地从位置j+1开始尝试。
代码：
1 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { 2 int start = 0; // 起始位置 3 int remain = 0; // 当前剩余燃料 4 int debt = 0; // 前面没能走完的路上欠的债 5 6 for (int i = 0; i < gas.size(); i++) { 7 remain += gas[i] - cost[i]; 8 if (remain < 0) { 9 debt += remain;10 start = i + 1;11 remain = 0;12 }13 }14 15 return remain + debt >= 0 ? start : -1;16 }
Leetcode# 134 Gas station
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。