leetcode-gas-station

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/gas-station/

　　一个环形有n个加油站，每个加油站能为汽车加油量不同，汽车在两站之间耗费油量也不同，假定汽车油桶足够大，问从哪个加油站出发，能不缺油地绕一个环形，如果不存在则返回-1

题目分析

　　暴力解法是O(n^2)，看了下disscuss区的解法https://discuss.leetcode.com/topic/39755/proof-of-if-total-gas-is-greater-than-total-cost-there-is-a-solution-c/2 主要是证明了两点：

  1. 如果sum(gas) >= sum(cost)，那么一定存在方案
  2. 在假定存在方案的前提下，算法不妨从0开始到n-1遍历，最小的累积sum(gas) - sum(cost)的位置为loc，那么loc+1即为出发点

　　这两点的证明在原帖中有很详细的解释。我觉得这种trick题真的是不看巧妙解法，自己很难想出来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = Integer.MAX_VALUE;
        int total = 0;
        int loc = 0;
        int i = 0;
        for (i = 0; i < gas.length; i++) {
            total += (gas[i] - cost[i]);
            if (total < sum) {
                sum = total;
                loc = i;
            }
        }
        if (total < 0) {
            return -1;
        }
        return (loc + 1) % gas.length;
    }
}

　　时间复杂度 O(n)