leetcode
leetcode 1701 ~ 1750
新增的最少台阶数

新增的最少台阶数

难度:

标签:

题目描述

代码结果

运行时间: 42 ms, 内存: 28.6 MB


// Java Stream API solution with detailed comments
// We aim to find the minimum number of additional rungs required so that no gap exceeds 'dist'.
import java.util.stream.IntStream;

public class LadderStream {
    public int addRungs(int[] rungs, int dist) {
        // Starting from the ground level
        int[] previousHeight = {0};

        return IntStream.of(rungs)
            .map(rung -> {
                // Calculate the number of rungs needed if the gap exceeds dist
                int needed = (rung - previousHeight[0] - 1) / dist;
                previousHeight[0] = rung; // Update previous height
                return needed;
            })
            .sum(); // Sum up the required rungs
    }
}

解释

方法:

该题解通过遍历数组 rungs 来检查相邻台阶之间的距离,从而确定是否需要插入新的台阶。变量 cur 表示当前所在的台阶高度,开始时设置为0(地面高度)。对于每个台阶 x,计算从 cur 到 x 的距离 m(m = x - cur)。如果 m 大于给定的最大距离 dist,则计算需要添加的台阶数,公式为 ((m + dist - 1) // dist - 1),其中用到了整除向上的技巧以确定覆盖 m 距离需要多少个 dist 长的步进。遍历结束后,变量 ans 将包含总共需要添加的台阶数。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算需要增加的台阶数时使用的公式是 ((m + dist - 1) // dist - 1),而不是直接使用 m // dist?
这个公式的使用是为了实现向上取整除法,从而准确计算必要的额外台阶数。如果直接使用 m // dist,则会得到向下取整的结果,这可能导致计算出的台阶数不足以覆盖从一个台阶到下一个台阶的距离。比如,如果 m = 5 且 dist = 3,直接除法得到 1,但实际上需要两个台阶(3 和 6)才能到达或超过 5。所以,使用 ((m + dist - 1) // dist - 1) 计算首先将 m 增加 dist - 1,这样除以 dist 后能够实现向上取整的效果。然后减 1 是因为这个计算包括了从当前台阶到下一个台阶的整个距离,而不是仅仅新增的台阶数。
🦆
题解中提到如果m大于dist才需要添加台阶,但如果m恰好等于dist,是否仍然能保证从当前台阶跳到下一个台阶?
是的,如果 m 恰好等于 dist,那么根据题目设定,这是可以直接从当前台阶跳到下一个台阶的最大距离。因此,在这种情况下,不需要添加新的台阶。只有当 m 大于 dist 时,才表明距离超出了单次跳跃所能达到的最大范围,这时候才需要添加额外的台阶来保证可以从一个台阶跳到下一个台阶。
🦆
题解中的方法是否考虑了从最后一个台阶再向上的情况?例如如果最后一个台阶和之前的台阶距离超过dist,是否需要在最后加入额外的台阶?
题解中的方法不需要考虑从最后一个台阶再向上的情况,因为题目的目标是确保能够到达每个给定的台阶,而不是超过它。题解中只考虑确保每一步都能从当前台阶达到下一个指定的台阶。因此,只要最后一个台阶能够通过之前的台阶达到,就不需要在最后添加额外的台阶。
🦆
在题解的实现中,变量cur是如何确保总是指向当前台阶或起始地面的?是否有可能出现误差累积导致计算错误?
在题解中,变量 cur 被初始化为0(地面的高度),并且在每次循环中,都会更新为最新处理过的台阶的高度 x。这样确保了 cur 总是表示当前的高度位置,无论是地面还是最近处理过的台阶。由于这种更新是直接赋值而非基于前一个值的计算,因此不会出现误差累积的问题。每次都是直接设置为具体的台阶高度,所以计算是准确的。

相关问题