0871. Minimum Number of Refueling Stops

题目信息

题号:

0871

难度:

Hard

主题:

行程、加油站、最少停靠

原题:

LeetCode 0871

重点:

汽车每行驶一英里消耗一单位燃料,只有到达站点后才能选择加入该站全部燃料;油箱容量不限

题目重述

汽车从位置 0 出发驶向位置 target,初始燃料为 startFuel。每行驶一英里消耗一单位燃料,油箱容量没有上限。

数组 stations[i] = [position_i, fuel_i] 按位置递增给出沿途加油站。汽车到达某个站后,可以选择停车并把该站的全部 fuel_i 加入油箱,也可以不停;同一站最多使用一次。请返回到达目标所需的最少加油次数,若无法到达则返回 -1。燃料恰好降为 0 时仍可到达该位置并在站点加油;恰好以零燃料到达目标也算成功。

1 <= target, startFuel <= 10^9,加油站数量不超过 500;0 < position_i < target,1 <= fuel_i <= 10^9,站点位置严格递增。

自建示例

三个站都必须使用:

输入:target = 100, startFuel = 25, stations = [[20,30],[50,40],[80,20]]
输出:3
解释:初始可到达 20;加油后可到达 50,再加油可到达 80,第三次加油后到达 100。跳过任一站都会在下一段耗尽燃料。

初始燃料恰好到达目标:

输入:target = 50, startFuel = 50, stations = []
输出:0
解释:汽车行驶 50 英里后燃料恰好变为 0,并已到达目标。到达时油量为零仍算成功,因此无需加油。