一、题目描述
二、解题思路
1.运动过程分析
这里需要一个油箱剩余油量的变量resGas,初始化resGas=0;还需要一个标记从什么位置当做初始位置的startIdx,初始化startIdx=0。
我们从数组下标idx=0处开始向后遍历,初始时startIdx=0,遇到下标为idx的加油站时,看邮箱内此时剩余油量能否到达下一个油站:
resGas=resGas+gas[i]-cost[i]
当resGas>=0时,可以到达下一个油站;
当resGas<0时,不可以到达下一个油站,此时也意味着从startIdx开始运动到达不了idx位置,从startIdx到idx之间的所有位置也同样不可达idx。此时把startIdx设置为idx+1。
这里用startIdx->idx小车运动不可达的图示解释一下上面标注黄色部分:
2.可以循环的条件判断
这里需要注意的是,小车从startIdx->加油站数组末尾时,如果可达,需要将idx=(idx+1)%gas.length,如果整个过程一直可达,等到二次循环idx+1==startidx时,意味着从startIdx开始行驶一定可以循环一周,返回startIdx。所以我们还要添加一个变量标注一下此时是否已经二次循环,实现代码内用newloop来标识。
3.不可以循环的条件判断
不存在循环一周的情况:当二次循环过程中还是出现了不可达的情况,那么就意味着不存在循环的情况,返回-1,图示:
就意味着从startIdx到末尾之间的元素和下标0到下标3之间的所有元素到下标3都不可达,此前已经确定了从下标0到下标4之间的元素已经不可达,所以肯定不能形成循环。
整个过程需要执行两次数组遍历,所以时间复杂度为O(n),效率还是可以的。
三、代码实现
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param gas int整型一维数组 * @param cost int整型一维数组 * @return int整型*/public int gasStation (int[] gas, int[] cost) {// 就从0开始寻找,设置油箱剩余量resGas,int len=gas.length;int startidx=0,residx=0;int resGas=0;//初始时油箱剩余油量为0int nowidx=0;boolean newloop=false;while(nowidx<len){int nowGas=resGas+gas[nowidx]-cost[nowidx];if(nowidx+1==len){newloop=true;}if(nowGas<0){//表示从startidx开始到达不了startidx=(nowidx+1)%len;resGas=0;if(newloop){residx=-1;break;}}else{//表示当前油量还可以支撑往后走resGas=nowGas;if(newloop&&((nowidx+1)%len==startidx)){residx=startidx;break;}}nowidx=(nowidx+1)%len;}return residx;}
}
四、刷题链接
加油站_牛客题霸_牛客网