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

• 871. 最低加油次数
• • 问题描述：
  • 解题思路：
  • 题解：
  • 提交结果：

示例 1：
输入：target = 1, startFuel = 1, stations = []
输出：0
解释：我们可以在不加油的情况下到达目的地。

示例 2：
输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：我们无法抵达目的地，甚至无法到达第一个加油站。

示例 3：
输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
我们出发时有 10 升燃料。
我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。
我们沿途在1两个加油站停靠，所以返回 2 。

我们不要理解成加油站，就当路上的不是加油站，而是一桶桶的油，每次经过的时候，就把油带上，为了保证最少加油次数，当油不够的时候我们就取身上最大的那桶油加上，这样如果身上没油了，那么就到不了了
简单来说就是一条直线，从起点到终点，距离起点station[i][0]的位置各有一个容量为station[i][1]的汽油桶，如果可以到达终点返回最少的加油次数，否则返回-1;

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
		}
	}
}