【刷题日记】871. 最低加油次数

本次刷题日记的第 78 篇，力扣题为：871. 最低加油次数，困难

一、题目描述：

最近油价高居不下，甚至还有上涨的趋势，我们今天就来计算一下达到目的地，如何加油次数最少，871. 最低加油次数

二、这道题考察了什么思想？你的思路是什么？

还是来看一下题目给了我们那些重要的信息:

• 汽车从出发地到目的地距离为 target ，汽车启动的时候，有油 startFuel 升，对应就可以跑 startFuel 英里

• 途中有很多个加油站，车子到每一个加油站，如果决定加油的话，则会将加油站所有的油全部加到车子油箱中，土豪吧

• 那么题目需要我们找到，从出发地到目的地最少的加油次数

分析

其实就这么来看，简单的想法是不是会想到，我的车开出去，前几个加油站我都加油，直到全部加的油能够跑 target 英里就可以了，这样岂不是很简单？

实际上稍微想想就知道，这样确实很省事，但是并不一定是最低的加油次数

那么一点，我们是可以明确的，那就是加油站相对出发地的距离，一定是递增的，而且对于每一个加油站，我们也能够间接知道我们当前是否可以跑到目的地，或者是间接知道，当前我是否需要加油，如何间接知道呢？我们可以倒推

例如咱们出发地的时候，dp [0] 就表示能够跑的英里数，自然 dp[0] = startFuel

那么我们令加油站的位置为 i，加油的次数为 j，那么我们就有

dp[j]=dp[j−1]+stations[i][1]dp[j] = dp[j-1] + stations[i][1] dp[j]=dp[j−1]+stations[i][1]

满足上述公式的前提是 dp[j-1] 是 >= stations[i][0] 的 ， 很明显，只有汽车中的油能够坚持到 stations[i][0] 的位置，才有机会加油，如果都没有机会坚持到加油站，那么何谈加油呢

那么我们推到 dp 的时候，我们如何来做到 dp 里面存储的数据，是能够满足加油次数最少的呢？

简单理解就是，我们在经过当前加油站的时候，要看当前不加油的话，是否能够满足到达下一个，或者下下个加油站，如果可以，那么肯定是到了哪个加油站再去加

可也会存在这么一个情况，当前不加油，到了之后的加油站才加，可能会出现加了油也没有办法到达目的地

因此我们可以这样来推导 dp，汽车走过每一个加油站的时候，来计算 dp 当到当前位置的最大值

target = 100, startFuel = 10,

[10,60],	[20,30],	[30,30],	[60,40]

例如上面这个例子

咱们推导出来，肯定是只在 第一个加油站和 第四个加油站加油，我们即可开到目的地，即加 两次油

开到第一个加油站的 dp 情况

dp[0]=10

dp[1]=70

开到第二个加油站的 dp 情况

dp[2]=100

开到第三个加油站的 dp 情况

dp[3]=130

dp[2]=100

开到第四个加油站的 dp 情况

dp[4]=170

dp[3]=140

dp[2]=110

剩下的就来看看代码的实现情况吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func minRefuelStops(target int, startFuel int, stations [][]int) int {

    
    dp := make([]int,len(stations)+1)
    dp[0] = startFuel

    for i,sta := range stations {
        // 这一层主要是确认 dp 实际应该存放的值，因为并不是每一个加油站我们都是要默认加油的，我们要尽可能的少加油
        for j:=i; j>=0 ;j--{
            if dp[j] >= sta[0] {
                dp[j + 1] = max(dp[j+1], dp[j] + sta[1])
            }
        }
    }

    for i,v := range dp {
        if v >= target {
            return i
        }
    }
    return -1

}

func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}

四、总结：

看咱们的实现方式，对于时间复杂度还是比较容易看出来的，时间复杂度是 O(n^2) ，嵌套了 2 层循环，第一层和第二层循环的次数都是加油站的个数 n

空间复杂度是 O(n) ， 我们开辟了 O(n) 的空间 dp 来帮助我们推到数据

原题地址：871. 最低加油次数

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~