1936-新增的最少台阶数

给你一个 严格递增 的整数数组 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 <= 105
1 <= rungs[i] <= 109
1 <= dist <= 109
rungs 严格递增

方法一：模拟 + 贪心

思路与算法

我们可以模拟爬台阶的过程。

每当计划爬上新一级台阶时，需要增设的台阶数目可以表示为当前位置与新一级台阶位置（目标位置）的高度差的函数。假设高度差为 d\ (> 0)，可直接到达的两个台阶的最大间隔为 dist。此时我们可以判断 d 与 dist 的大小来判断是否需要新增台阶。

如果 d \le \textit{dist，此时无需新增台阶。如果 d > \textit{dist，此时无法直接到达，我们可以每隔 dist 高度插入新台阶，直至新台阶与目标位置的间隔不大于dist。显然，这种方案所需增设台阶数目最小，对应的需要增设台阶数目为

\left\lfloor d - 1}{\textit{dist} } \right\rfloor.

上式当 0 < d \le \textit{dist 时为 0，与对应情况相符，因此实际计算时无需额外讨论 d 与 dist 的大小关系。

由于台阶数组 rungs 严格递增，因此我们将当前高度初值设为 0，并按顺序遍历 rungs 数组以模拟爬台阶的过程。每当遍历到新一级台阶时，我们计算与当前位置的高度差，进而计算最少需要增设的台阶数目，并将当前高度更新为新一级台阶的高度。我们维护这些台阶数目的总和，并最终返回作为答案。

代码

[sol1-C++]class Solution {
public:
    int addRungs(vector<int>& rungs, int dist) {
        int res = 0;   // 需要增设的梯子数目
        int curr = 0;   // 当前高度
        for (int h: rungs){
            // 遍历数组计算高度差和最少添加数目，并更新当前高度
            int d = h - curr;
            res += (d - 1) / dist;
            curr = h;
        }
        return res;
    }
};

[sol1-Python3]class Solution:
    def addRungs(self, rungs: List[int], dist: int) -> int:
        res = 0   # 需要增设的梯子数目
        curr = 0   # 当前高度
        for h in rungs:
            # 遍历数组计算高度差和最少添加数目，并更新当前高度
            d = h - curr
            res += (h - curr - 1) // dist
            curr = h
        return res

复杂度分析

时间复杂度：O(n)，其中 n 为数组 rungs 的长度。即为遍历数组计算需要增设台阶数目的时间复杂度。
空间复杂度：O(1)。