题目大意：
加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -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 升汽油。 因此，无论怎样，你都不可能绕环路行驶一周。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=134
解题思路分析：
本题可以使用暴力解来解题。分别尝试从每一个点出发，在当前点加满所有该加油站的油，然后再看目前油箱中的油能否开到下一个加油站，如果不能，继续尝试从下一个点出发。反之，如果可以，则用油箱中的油减去开到下一站的油耗，继续查看，当车子一直能开回到起点，说明该起点是合理解，返回该起点坐标。如果循环完所有起点都无法开回到该起点，返回-1。
该暴力解法，需要循环每一个点当做起点，并且从每一个起点出发，最坏情况都要遍历完每一站，因此代码的时间复杂度是O(n^2)，虽然可以通过TC，但是为了精益求精，我们需要考虑尝试为该算法剪枝。试想，假如我们可以从加油站0开到加油站5，之后再想开到加油站6时，由于剩余油量不足，而导致该起点（加油站0）无效时，接下来，加油站1-5其实都是无法作为起点的。原因很简单，当从加油站0出发时，到达加油站1-5时，油箱剩余油量肯定是大于等于0，即使这样也无法开到加油站6，那么从加油站1-5出发时，起始油量均为0，肯定也无法开到加油站6，因此，该情况下，1-5可以跳过，到达剪枝效果。
实现代码：
public int canCompleteCircuit(int[] gas, int[] cost) {
// 循环每一个点作为出发点
for(int i=0;i<gas.length;i++){
// 当前油箱中油量
int tank = 0;
// 已经经过的加油站
int count=0;
// 当前位置
int current = i;
// 加油站个数
int length=gas.length;
// 当经过的加油站个数小于总个数
while(count<length){
// 将当前加油站的所有油加入油箱
tank+=gas[current];
// 如果当前油箱中油量不足以开到下一站，退出
if(tank<cost[current]) break;
// 开到下一站，邮箱中油量减去，油量消耗
tank-= cost[current];
// 如果下一站的编号等于总个数，循环至加油站0
if(current+1==length) current=0;
else current++; // 反之加油站编号加一
// 如果经过的加油站个数等于总个数，说明已经回到起点，返回起点坐标
if(++count==length) return i;
} // 循环结束时，说明该起点无效
// 如果当前起点线路的终点坐标小于当前起点，说明后续的点都已经遍历过，退出
if(current<i) break;
// 跳过中间无效的起点。
else i=current;
}
return -1;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Gas Station.
Memory Usage: 44.8 MB, less than 5.88% of Java online submissions for Gas Station.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-134-gas-station-解题思路分析/