题目描述:
代码实现:
- 贪心算法,设置一个sum来计算gas是否大于等于cost,再设置一个curSum来判断从哪里为起始点,并设置为startIndex,最终得出结果。
- 时间复杂度:O(n)
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function(gas, cost) {
var sum = 0, curSum = 0, startIndex = 0
for (var i = 0; i < gas.length; i++ ) {
sum += gas[i] - cost[i]
curSum += gas[i] - cost[i]
if (curSum < 0) {
curSum = 0
startIndex = i + 1
}
}
return sum >= 0 ? startIndex : -1
};