[LeetCode]Gas Station

这个问题的突破点就是如果在一个可以开始的station x开始，到了y发现没有办法前进了，那么在x和y之间所有的点开始都不可能过y。
原因是从x开始到任何x和y之间的station i，gas都是有余裕的，从i开始砍掉start 到 i那一部分的话，就缺少了一部分gas，更不可能过y了。所以算法就是，设diff为gas的存量，从0开始，如果diff大于0的话，就去下一个station更新diff；如果diff小于0的话，start station设为下一个station，diff设为0。如果我们发现转了一圈，就说明当前返回start station的index。如果我们停在了大于len的位置，则说明没有可以转一圈的station。这样我们最多转2圈，转 2 * len - 1个station，时间复杂度是O（n）。
代码如下：

	public class Solution {
	public int canCompleteCircuit(int[] gas, int[] cost) {
	if (gas == null || cost== null)
	return -1;
	int diff = 0;
	int len = gas.length;
	int start = 0;
	for (int i = 0; i <= 2 * len - 1; i++) {
	diff += (gas[i % len] - cost[i % len]);
	if (diff < 0) {
	if (i >= len - 1)
	break;
	else {
	diff = 0;
	start = i + 1;
	}
	} else {
	if (i - start == len)
	return i % len;
	}
	}
	return -1;
	}
	}

view raw gas station.java hosted with ❤ by GitHub