加油站问题.md

加油站问题（gas-station）

知识点：贪心 ## 题目描述

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.

在一条循环路线上有N个加油站，索引为i的加油站具有的油量为gas[i]。 你有一辆具有不限容量油箱的小汽车，并且这辆车从第i个加油站到第i+1个加油站耗费的油量是cost[i]，初始的时候你的小汽车的油箱里面没有油，你需要寻找一个站点作为起点。 如果从某个起点出发可以保证你开着你的车绕着赛道走一圈，则返回起点的加油站下标，否则返回-1 返回起点加油站的下标。

比如下图：

加油站上的数字代表该加油站具有的油量，圆圈上的数字代表该路段需要耗费的油量，那么小车该从哪个加油站出发才能保证顺利走一圈呢？

注意：给出的实例可以保证解决方案是唯一的。

解题思路

简单地想，我们当然是想从第1个加油站出发，到达下一个加油站时车里剩余的油尽可能多，这样车里剩下的油还可以继续后面的路程，所以，采取贪心的思路，首先计算从每一站出发，到达下一站后车里还能剩余的油，然后按照剩余油的多少进行排序，从可以剩余油最多的站出发，进行模拟行程，看最后可否走一圈，如果不可以，则换下一个起点。

代码

核心代码：

public int canCompleteCircuit(int[] gas, int[] cost) {

        //remaining为二维数组，remaing[index][0]代表车从第index出发到达index+1站后里面可以剩余的油，
        // remaing[index][1]=index，因为后面要对remaing按照remaing[index][0]即剩余的油量排序，
        // 所以要把原始的索引记录下来，排完序后直接从remaing[index][0]最大的值对应的remain[index][1]处开始开车即可
        int[][] remaining = new int[gas.length][2];

        //gas[i]---->gas[i+1]  cost[i]，计算remaining
        for (int index = 0; index < gas.length; index++) {
            remaining[index][0] = gas[index] - cost[index];
            remaining[index][1] = index;
        }

        //按照remaining[index][0]对remaing进行排序
        QuickSort(remaining, gas.length);

        //由于上面排完序是降序，所以这里从后往前遍历
        for (int index = gas.length - 1; index >= 0; index--) {
            //如果剩余的油大于等于0，说明油足够到达下一站
            if (remaining[index][0] >= 0) {
                if (helper(gas, cost, remaining[index][1])) {
                    return remaining[index][1];
                }
            } else {
                return -1;
            }
        }


        return -1;
    }

    //模拟从第startIndex站出发，看能不能走完全程
    boolean helper(int[] gas, int[] cost, int startIndex) {
        int count = 0;
        int curGas = 0;
        for (int index = startIndex; count <= gas.length; count++, index = (index + 1) % gas.length) {
            curGas += gas[index];
            if (curGas >= cost[index]) {
                curGas -= cost[index];
            } else {
                return false;
            }
        }

        return true;
    }
    

可以求得上例中的答案为0，即从第0号加油站出发，就像下面这样：

完整代码