贪心之加油站

134. 加油站

为了能够使车可以达到下一站，必须满足：已有油量 >= 达到下一站所需油量

给出一个样例：gas = [4, 3, 1, 2, 7, 4]; cost = [1, 2, 7, 3, 2, 5]

当我们经过第i个加油站，其油量的变化为：gas[i] - cost[i]

可以计算出经过每个加油站的变化值：[3, 1, -6, -1, 5, -1]

假设从第0个加油站开始，以变化的累积值绘制图像：

当折线全部在 X 轴上方时，才表示可以从起点顺利到达终点！！显然从第0个加油站开始，不可以绕环路行驶一周

那我们从哪个点开始最可能使折线全部在 X 轴上方呢？

根据上图，当x = 4时，是最有可能使折线全部在 X 轴上方的，如下图所示：

下面给出完整代码：

public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    int sum = 0, min = 10010, idx = -1;
    for (int i = 0; i < n; i++) {
        sum += gas[i] - cost[i];
        if (sum < min) {
            min = sum;
            idx = i + 1;
        }
    }
    if (sum < 0) return -1;
    return idx % n;
}