Skip to content

Latest commit

 

History

History
131 lines (82 loc) · 4.74 KB

0871._Minimum_Number_of_Refueling_Stops.md

File metadata and controls

131 lines (82 loc) · 4.74 KB

871. Minimum Number of Refueling Stops

难度: Hard

刷题内容

原题连接

内容描述

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

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

看到这道题就想到了前几天做的gas station

这种题我有一种感觉了，就是先将station排序然后遍历一遍，每碰到一个station都会有两种或者三种情况，最终遍历完还要check一些东西结束

所以这道题目首先station是已经有序的，并且0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

我们定义一个起点名为start_point,当前的燃料cur_fuel,然后最重要的就是贪心思想维护一个station含油量的最大堆， 每次油不够我们自然而然取堆顶元素补充燃料

对于每一个station：

  1. 如果当前位置加上当前燃料能够到达当前station，那么： - 燃料更新，减去 station[0] - start_point - 位置更新为 station[0]
  2. 如果当前位置加上当前燃料不能到达当前station，那么： - 只要我们不能到达，就一直从堆里去燃料，直到能到达或者堆空了，如果while循环出来发现还是不能达到（即因为堆空退出的循环），立刻返回 -1
  3. 一定要记得将当前station的燃料加到堆里面去，以便后面不够的时候取用

现在，我们走完了所有station，但是最后一个station的位置也是小于target的，我们还要看是否能走到target

所以我们首先将当前燃油全部耗尽，如果还是不够就看看堆里面还能不能补充，如果while循环出来发现还是不能达到（即因为堆空退出的循环），立刻返回 -1； 如果最终达到了target，那么我们返回总的station个数与堆内元素的差值（即我们已经加了油的station个数）。

beats 99.07%

class Solution(object):
    def minRefuelStops(self, target, startFuel, stations):
        """
        :type target: int
        :type startFuel: int
        :type stations: List[List[int]]
        :rtype: int
        """
        from heapq import heappush, heappop
        not_fueled, start_point, cur_fuel = [], 0, startFuel
        for station in stations:
            if start_point + cur_fuel >= station[0]:
                cur_fuel -= station[0] - start_point
                start_point = station[0]     
            else:
                while not_fueled and start_point + cur_fuel < station[0]:
                    cur_fuel += -heappop(not_fueled)
                if start_point + cur_fuel < station[0]:
                    return -1
            heappush(not_fueled, -station[1])
        start_point += cur_fuel
        while not_fueled and start_point < target:
            start_point += -heappop(not_fueled)
        if start_point < target:
            return -1
        return len(stations) - len(not_fueled)