题目描述:

加油站 - 图1

代码实现:

  • 贪心算法,设置一个sum来计算gas是否大于等于cost,再设置一个curSum来判断从哪里为起始点,并设置为startIndex,最终得出结果。
  • 时间复杂度:O(n)
  1. /**
  2. * @param {number[]} gas
  3. * @param {number[]} cost
  4. * @return {number}
  5. */
  6. var canCompleteCircuit = function(gas, cost) {
  7. var sum = 0, curSum = 0, startIndex = 0
  8. for (var i = 0; i < gas.length; i++ ) {
  9. sum += gas[i] - cost[i]
  10. curSum += gas[i] - cost[i]
  11. if (curSum < 0) {
  12. curSum = 0
  13. startIndex = i + 1
  14. }
  15. }
  16. return sum >= 0 ? startIndex : -1
  17. };

加油站 - 图2