134. 加油站
在一条环路上有 n
个加油站,其中第 i
个加油站有汽油 gas[i]
升。
你有一辆油箱容量无限的的汽车,从第 i
个加油站开往第 i+1
个加油站需要消耗汽油 cost[i]
升。你从其中的一个加油站出发,开始时油箱为空。
给定两个整数数组 gas
和 cost
,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1
。如果存在解,则 保证 它是 唯一 的。
思路:
从i位置开始,用step表示可以移动的距离,当step=n的时候,表示可以走一圈,则返回i即可。利用a记录从i位置开始走step步后所剩下的汽油,若a>=0,则表示还能继续走,反之,则表示已经没油了,这样的话从i位置就不能实现走一圈。
优化:
当a<0的时候,可以知道在上述思路的情况下,是从i+1位置重新出发,但是从i位置到i+step不能通过,则从i+1位置到i+step一定也不能通过,因为既然可以从i到i+step,就表示i位置一定是能出发的,这就意味着gas[i]>=cost[i],而去掉gas[i]和cost[i]所带来的影响后,到从i+1到i+step的a一定更小,因为失去了gas[i]-cost[i]>0,因此可以直接从i+step+1位置处重新开始寻找。
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {// //n^2做法// int n=gas.size();// int l=0,r=0;// for(int i=0;i<n;i++)// { // int flag=0;// int begin=i;// int allgas=gas[i];// while(1)// {// allgas-=cost[begin];// if(allgas<0)// break;// begin++;// begin%=n;// if(begin==i)// return i;// allgas+=gas[begin];// }// }// return -1;//n的做法?int n=gas.size();for(int i=0;i<n;i++){int a=0;int step=0;for(;step<n;step++){int index=(i+step)%n;a=a+gas[index]-cost[index];if(a<0){ break;}}if(a>=0)return i;i+=step;}return -1;}
};