# Gas Station

2017-10-14

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

Discuss 区有人给出了 $O(n)$ 的方法： https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas.

## 两个结论

1. 如果从 i 点出发，恰好无法到达 j 点（即能到达 j 前一点但无法到达 j 点），则如果从 i ~ j 之间任意一点出发，均无法到达 j 点。

…, i, i + 1, …, j - 1, j, …

1. 如果所有车站的油量总和大于等于所有车站到下一站需要的油量总和，即

$$\sum_{i=0}^{N-1} gas[i] \ge \sum_{i=0}^{N-1} cost[i]$$

则问题必有解。

• 若两点均满足 $gas[i] \ge cost[i]$，显然结论成立

• 若某一点不满足 $gas[i] \ge cost[i]$，不妨设 $gas[0] < cost[0]$，由于$gas[0] + gas[1] \ge cost[0] + cost[1]$，则必有$gas[1] > cost[1]$，那么从 1 点出发可以到达 0 点并回到 1 点，结论仍成立

1. 把相邻的好点结合为新的好点，相邻的坏点结合为新的坏点，得到一个好点坏点相间的环

2. 把好点和下一个坏点结合，得到 $N'$ 个点，由于 $\sum_{i=0}^{N-1} gas[i] \ge \sum_{i=0}^{N-1} cost[i]$，保证了至少有一个好点

## 实现源码

https://github.com/qianbinbin/leetcode

LeetCode算法

Single Number II