贪心之加油站

力扣1220

package com.zhang.reflection.面试.算法模版.贪心算法;
/**
 * 在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，
 * 从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。
 *
 * 请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。
 * 题目数据可以保证最多有一个答案。
 *
 * [1,2,3,4,5],[3,4,5,1,2]
 * 3
 */
public class 加油站 {
    /**
     * 选择出发点，累加计算每一站得到的汽油量和消耗的汽油量，一旦有
     *
     * sumCost > sumGas，就需要遍历下一个起始节点，但是这里需要用到贪心算法，否则会超出时间限制。
     *
     * 假设有两个站点x和y，如果x到不了y+1（但能到y），那么从x到y的任一点出发都不可能到达y+1。原因如下：
     *
     * 设x、y之间一点为a，从x出发到y积累的油一定比从a出发到y积累的油多，因为从x出发到a积累的油一定是非负的，
     * 设remain表示积累的油，即remain(x -> y) = remain(x -> a) + remain(a -> y)，因为都能到达，三项都是非负的，
     * 必然有remain(x -> y) >= remain(a -> y)，因此a点必然到不了y+1，所以在以下的代码中，不能是i += 1，而是i += count + 1，
     * 直接跳过中间count个节点。
     */
    public int gasStation (int[] gas, int[] cost) {
        // write code here
        int n=gas.length;
        int rest=0;
        int start=0,sum=0;
        for(int i=0;i<n;i++){
            rest+=gas[i]-cost[i];
            sum+=gas[i]-cost[i];
            if(rest<0){
                start=(i+1)%n;
                rest=0;
            }
        }
        return sum>=0?start:-1;
    }
}