题解 | #加油站#

题意整理

n个加油站排成一圈，每一个站点有对应的油，存储在gas数组，从一个站点走到下一个站点需要若干油量，存储在cost数组。
问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回-1。

方法一（枚举起始站点）

1.解题思路

首先枚举所有可能的起始加油站。如果剩余油量大于等于0，则进入内层循环，确定当前起始站点是否合法。
每次检查当前剩余油量rest。如果小于0，则不合法，终止循环。如果每次都大于等于0，则当前起始站点合法，返回对应加油站。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        //站点总数量
        int n=gas.length;
        //枚举起始站点
        for(int start=0;start<n;start++){
            //剩余油量大于等于0，才能继续往后走
            if(gas[start]>=cost[start]){
                //rest表示当前剩余油量
                int rest=gas[start]-cost[start];
                //模拟往后走一圈
                for(int i=start+1;i<start+n;i++){
                    //更新rest
                    rest+=gas[(i+n)%n]-cost[(i+n)%n];
                    if(rest<0){
                        break;
                    }
                }
                //走完一圈rest还大于等于0，则为合法起始站点
                if(rest>=0){
                    return start;
                }
            }
        }
        return -1;
    }
}

3.复杂度分析

时间复杂度：两层循环，最多执行 $n * n$ 次，所以时间复杂度是 $O (n^{2})$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。

方法二（贪心）

1.解题思路

定义一个rest记录汽车油箱剩余油量。定义一个sum表示恰好走完一圈后剩余油量。
遍历所有站点，更新rest和sum。如果剩余油量小于0，则跟换起始站点，重置rest。
最后如果sum大于等于0，说明总有一个起始站点合法，返回对应起始站点，否则，返回-1。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        //加油站个数
        int n=gas.length;
        //汽车油箱剩余油量
        int rest=0;
        //start指向起始加油站，sum表示恰好走完一圈后剩余油量
        int start=0,sum=0;
        for(int i=0;i<n;i++){
            //更新rest和sum
            rest+=gas[i]-cost[i];
            sum+=gas[i]-cost[i];
            //如果剩余油量小于0，则跟换起始站点，重置rest
            if(rest<0){
                start=(i+1)%n;
                rest=0;
            }
        }
        return sum>=0?start:-1;
    }
}

3.复杂度分析

时间复杂度：只需一层循环，总共执行n次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。