加油站

LeetCode-134

/**
 * 贪心算法
 * 先计算一遍所有加油站的总油量和总消耗油量，如果总油量小于总消耗油量，那么一定无法完成绕行操作，直接返回-1。
 *
 * 否则，总油量和总消耗油量之差就是我们可行驶的距离
 * 我们可以从任意一个加油站开始出发，当走过第i个加油站时，我们计算当前车上的油量与到下一个加油站的路程之差: remain += gas[i] - cost[i];如果这个值小于0, 那么说明我们无法从当前加油站到达下一个加油站，因此起点一定不可能在这些加油站中间。
 * 我们可以将起点设置为下一个加油站，并将油量清零，重新开始计算。当遍历完所有加油站后，如果车上的油量大于等于0，则说明从起点开始绕一圈是可行的，返回起点的索引即可。
 */
var canCompleteCircuit = function (gas = [], cost = []) {
  let remain = 0 // 当前车上的油量(余量)
  let totalGas = 0 // 所有加油站的总油量
  let totalCost = 0 // 所有加油站的总消耗油量
  let start = 0 // 起点索引

  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i]
    totalCost += cost[i]
    remain += gas[i] - cost[i]

    // temp 小于 0 说明汽油费不够，将起始点往前走一个(不是start++)
    if (remain < 0) { // 当前车上的油量不足以到达下一个加油站
      start = i + 1 // 将起点设置为下一个加油站
      remain = 0 // 油量清零，重新开始计算
    }
  }

  return totalGas >= totalCost ? start : -1
}