1936 新增的最少台阶数（贪心）

- 日理万妓 2022-08-30 01:46 101阅读 0赞

**1. 问题描述：**

给你一个严格递增的整数数组 rungs ，用于表示梯子上每一台阶的高度 。当前你正站在高度为 0 的地板上，并打算爬到最后一个台阶。另给你一个整数 dist 。每次移动中，你可以到达下一个距离你当前位置（地板或台阶）不超过 dist 高度的台阶。当然，你也可以在任何正整数高度处插入尚不存在的新台阶。返回爬到最后一阶时必须添加到梯子上的最少台阶数。

**示例 1：**

输入：rungs = \[1,3,5,10\], dist = 2  
输出：2  
解释：  
现在无法到达最后一阶。  
在高度为 7 和 8 的位置增设新的台阶，以爬上梯子。  
梯子在高度为 \[1,3,5,7,8,10\] 的位置上有台阶。

**示例 2：**

输入：rungs = \[3,6,8,10\], dist = 3  
输出：0  
解释：  
这个梯子无需增设新台阶也可以爬上去。

**示例 3：**

输入：rungs = \[3,4,6,7\], dist = 2  
输出：1  
解释：  
现在无法从地板到达梯子的第一阶。  
在高度为 1 的位置增设新的台阶，以爬上梯子。  
梯子在高度为 \[1,3,4,6,7\] 的位置上有台阶。

**示例 4：**

输入：rungs = \[5\], dist = 10  
输出：0  
解释：这个梯子无需增设新台阶也可以爬上去。

**提示：**  
1 <= rungs.length <= 10 ^ 5  
1 <= rungs\[i\] <= 10 ^ 9  
1 <= dist <= 10 ^ 9  
rungs 严格递增

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/add-minimum-number-of-rungs

**2. 思路分析：**

我们可以结合例子先画画图，可以发现要想使得插入的新台阶的数量是最少的，取决于三个变量的值，分别是起点的高度s，当前台阶的高度rungs\[i\]，当前能够跨的最大距离dist，如果当前起点的高度加上能够跨的最大距离大于等于当前台阶的高度的话那么肯定是可以到达当前的台阶的，这个时候我们不用插入新的台阶，我们的原则是能不插入台阶就不插入台阶，也即尽量每一次到达已有台阶的位置，这样使用的台阶数肯定是最少的，当我们无法从当前的起点跨到当前台阶的时候说明我们需要插入新的台阶，这里需要计算一下需要的台阶的数目，需要判断一下（rungs\[i\] - s）% d的余数，如果余数为0说明恰好能够到达，说明需要的台阶数为 （rungs\[i\] - s） // d - 1，可以举一下具体的例子会比较好理解（rung = \[2，6\], d = 2需要1个高度为4的台阶），余数不为0的时候那么需要的台阶数为（rungs\[i\] - s） // d。为什么上面的贪心所以为什么每一次不跨大一点的步数呢？尽可能到达已有的台阶。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 主要看相邻两个梯子是否可以到达, 贪心
        def addRungs(self, rungs: List[int], d: int) -> int:
            s = 0
            n = len(rungs)
            i, res = 0, 0
            while i < n:
                if s + d >= rungs[i]:
                    # 当前的起点变为台阶的高度
                    s = rungs[i]
                    i += 1
                else:
                    # 判断起点与当前台阶需要插入的新的台阶的数量
                    if (rungs[i] - s) % d == 0:
                        res += (rungs[i] - s) // d - 1
                    else:
                        res += (rungs[i] - s) // d
                    # 插入新的台阶之后当前的起点变为台阶的高度
                    s = rungs[i]
                    i += 1
            return res