加油站

发表于2024-05-17更新于2024-05-17

加油站

https://leetcode.cn/problems/gas-station/description/

图 0

思路

1、首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

2、每一站的剩余油量rest[i] = gas[i]-cost[i]

3、i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

图 1

4、那么为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。

那有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？ 如图：
图 2

如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。

区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择其实位置了。

那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

局部最优可以推出全局最优，找不出反例，试试贪心！

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var canCompleteCircuit = function(gas, cost) {
  let rem = []
  for(let i=0;i<gas.length;i++){
    rem.push(gas[i]-cost[i])
  }
  let sum = rem.reduce((a,b)=>a+b,0)
  if (sum<0) return -1
  let cursum = 0
  let start = 0
  for(let i=0;i<rem.length;i++){
    cursum += rem[i]
    if (cursum<0){
      start = i+1
      cursum = 0
      continue
    }
  }
  return start
};
1
2
3
4
5
6
7
8
9
10
11
12
13
// 更优解，ai根据我上面的代码做的简化，只需一层for循环
var canCompleteCircuit = function(gas, cost) {
  let total = 0, sum = 0, start = 0;
  for(let i = 0; i < gas.length; i++){
    total += gas[i] - cost[i];
    sum += gas[i] - cost[i];
    if(sum < 0){
      start = i + 1;
      sum = 0;
    }
  }
  return total < 0 ? -1 : start;
};