新增的最少台阶数
难度:
标签:
题目描述
代码结果
运行时间: 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恰好等于dist,是否仍然能保证从当前台阶跳到下一个台阶?
▷🦆
题解中的方法是否考虑了从最后一个台阶再向上的情况?例如如果最后一个台阶和之前的台阶距离超过dist,是否需要在最后加入额外的台阶?
▷🦆
在题解的实现中,变量cur是如何确保总是指向当前台阶或起始地面的?是否有可能出现误差累积导致计算错误?
▷