006.加油站

• 134.加油站
  • 贪心思路一
  • 贪心思路二

贪心思路一 §

func canCompleteCircuit(gas []int, cost []int) int {
	sum := 0
	minSum := 0
	for i := 0; i < len(gas); i++ {
		diff := gas[i] - cost[i]
		sum += diff
		if sum < minSum {
			minSum = sum
		}
	}
 
	if sum < 0 {
		return -1
	}
	if minSum >= 0 {
		return 0
	}
	for i := len(gas) - 1; i >= 0; i-- {
		diff := gas[i] - cost[i]
		minSum += diff
		if minSum >= 0 {
			return i
		}
	}
	return -1
}

贪心思路二 §

func canCompleteCircuit(gas []int, cost []int) int {
	totalSum := 0
	curSum := 0
	idx := 0
	for i := 0; i < len(gas); i++ {
		curSum += gas[i] - cost[i]
		if curSum < 0 {
			totalSum += curSum
			curSum = 0
			idx = i + 1
		}
	}
	totalSum += curSum
 
	if totalSum < 0 {
		return -1
	}
	return idx
}