每日一题(2022-07-02)——最低加油次数

func minRefuelStops(target int, startFuel int, stations [][]int) int {
	// 如果初始状态的油量就可与到达，返回0
	if target <= startFuel {
		return 0
	}
	remainOil := startFuel // 剩下的汽油
	pos := make([]int, 0) // 身上的油桶
	visited := make(map[int]bool) // 该位置的油桶是否已经拾起，如果已经拾起，就忽略，否则就带到身上。
	ans := 0 // 加油次数

	for { // 如果没有油了
		if target > remainOil {
			// 遍历路上油桶，拾起路过的油桶
			for _, distance := range stations {
				// 当前油量 可以路过带上的油桶 并且 之前没有带过这个油桶
				if remainOil >= distance[0] && visited[distance[0]] != true {
					// 标记已经带在身上的油桶
					visited[distance[0]] = true
					pos = append(pos, distance[1])
				}
			}
			// 因为 到这里的话 意味着 target > remainOil
			// len(pos) == 0：此时如果路上没有可与拾起的油桶
			// 代表旅程结束，终点无法到达。
			if len(pos) == 0 {
				return -1
			}
			sort.Ints(pos)
			remainOil = remainOil + pos[len(pos)-1]
			ans++
			// 这个油桶用过了 就丢掉
			pos = pos[:len(pos)-1]
		} else {
			return ans
		}
	}
}