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``,站点位置严格递增。 自建示例 -------- 三个站都必须使用: .. code-block:: text 输入:target = 100, startFuel = 25, stations = [[20,30],[50,40],[80,20]] 输出:3 解释:初始可到达 20;加油后可到达 50,再加油可到达 80,第三次加油后到达 100。跳过任一站都会在下一段耗尽燃料。 初始燃料恰好到达目标: .. code-block:: text 输入:target = 50, startFuel = 50, stations = [] 输出:0 解释:汽车行驶 50 英里后燃料恰好变为 0,并已到达目标。到达时油量为零仍算成功,因此无需加油。