作者： 負雪明燭
id： fuxuemingzhu
個人博客： http://fuxuemingzhu.cn/

---

目錄

• • 題目描述
  • 題目大意
  • 解題方法
  • • 貪心算法
  • 日期

題目地址：https://leetcode.com/problems/minimum-number-of-refueling-stops/

題目描述

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = [] Output: 0 Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]] Output: -1 Explanation: We can't reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] Output: 2 Explanation: We start with 10 liters of fuel. We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas. Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target. We made 2 refueling stops along the way, so we return 2.

Note:

1 <= target, startFuel, stations[i][1] <= 10^9

0 <= stations.length <= 500

0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

題目大意

一個車剛開始的時候有一些油，現在在一條直線上有一些加油站，第i個加油站距離出發點的距離和儲油量是station[i][0]和station[i][1]，假設汽車的油箱是無限大的，現在求從出發點出發能否到達結束點target，如果可以的話，需要經歷的最少加油站是多少。

解題方法

貪心算法

這個題是我遇到的騰訊面試題和2019年百度筆試題。

這個題的直觀思路是當油箱剩的有油的時候，不能遇到加油站就去加油，因為可能在油用完之前遇到另一個存油量很多的加油站。所以在這個思路下，如何解呢？

這個題的方法是，我們使用一個大根堆保存所有經歷過的加油站的存量，也就相當于把油放到后備箱里（注意不是油箱）。當我們無法到達某個加油站的時候，就是在半路熄火了，此時應該從后備箱中拿出最大的那個油桶進行加油，如果仍然不夠到達加油站，則繼續把后備箱的油拿出來加上。

所以，如果把后備箱的油全部都拿出來用完了仍然不能到達加油站的情況下，則返回-1.否則，由于是個貪心策略，所以使用了最少的加油站的油。

代碼的思路是，使用一個大根堆保存經歷過的加油站的油量，即放到了后備箱里。使用prev保存上一個加油站的位置，對所有的加油站進行遍歷，判斷從上一個加油站到當前加油站需要用掉多少油，如果油箱不夠用了則貪心使用后備箱中最大的油桶。當后備箱的油全部用完了，仍然不能到達現在的加油站，則返回-1。

注意，python的heapq默認是小根堆，如果想用大根堆，需要在放入數字的時候添加負號。

Python代碼如下：

class Solution(object):def minRefuelStops(self, target, startFuel, stations):""":type target: int:type startFuel: int:type stations: List[List[int]]:rtype: int"""# [pos, fuel]stations.append([target, float("inf")])# -fuelque = []pos = 0tank = startFuelres = 0prev = 0for p, g in stations:tank -= p - prevwhile que and tank < 0:tank += -heapq.heappop(que)res += 1if tank < 0:return -1heapq.heappush(que, -g)prev = preturn res

參考資料：https://leetcode.com/problems/minimum-number-of-refueling-stops/solution/

日期

2019 年 4 月 3 日 —— 好久不刷題了，越來越手生

總結

以上是生活随笔為你收集整理的【LeetCode】871. Minimum Number of Refueling Stops 解题报告（Python）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。