加油站

题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油gas[i]，并且从第_i_个加油站前往第_i_+1个加油站需要消耗汽油cost[i]。
你有一辆油箱容量无限大的汽车，现在要从某一个加油站出发绕环路一周，一开始油箱为空。
求可环绕环路一周时出发的加油站的编号，若不存在环绕一周的方案，则返回-1。

思路

贪心。
从起点出发，每次判断能否到达下一站，如果能，出发。不能，将下一站设为起点。
如果中途发现到不了下一站了，那么之前经过的任意一站都无法作为起点，因为这次旅途的起点就是满足出发条件的，既然到中途发现到不了下一站了，那么从中间站点出发到当前站肯定也到不了下一站。
如果在最后一站失败，直接失败，因为之前所有的站多作为起点试过了
如果最后一站没失败，可能需要从最后一站到起点站继续行驶，当行驶到起点，则成功。

如果当前能从当前站出发，就出发。即，利用贪心，每次都做最利于当前情况的选择

代码

public int canCompleteCircuit(int[] gas, int[] cost) {
        // write your code here
        int start = 0;  
        int last = 0;       // 行驶到当前位置剩余油量
        
        for(int i = start; i < gas.length; i++) {
            if((gas[i]+last-cost[i]) >= 0) {
                last = gas[i]+last-cost[i];     // 继续行驶
            }else {
                if(i == gas.length-1) {
                    return -1;      // 如果跑到最后一站失败了，就真的失败了
                }
                start = i+1;        // 选择从下一个加油站出发
                last = 0;
            }    
        }
        
        if(start != 0) {    // 不是从起点出发,继续行驶
            for(int j = 0; j < start; j++) {
                if((gas[j]+last-cost[j]) >= 0) {
                    last = gas[j]+last-cost[j];
                }else {
                    return -1;      
                }
            }
            return start;
        }else {
            return 0;   // 从起点出发的
        }
    }

考察点

• 贪心