Welcome to Subscribe On Youtube
1936. Add Minimum Number of Rungs
Description
You are given a strictly increasing integer array rungs
that represents the height of rungs on a ladder. You are currently on the floor at height 0
, and you want to reach the last rung.
You are also given an integer dist
. You can only climb to the next highest rung if the distance between where you are currently at (the floor or on a rung) and the next rung is at most dist
. You are able to insert rungs at any positive integer height if a rung is not already there.
Return the minimum number of rungs that must be added to the ladder in order for you to climb to the last rung.
Example 1:
Input: rungs = [1,3,5,10], dist = 2 Output: 2 Explanation: You currently cannot reach the last rung. Add rungs at heights 7 and 8 to climb this ladder. The ladder will now have rungs at [1,3,5,7,8,10].
Example 2:
Input: rungs = [3,6,8,10], dist = 3 Output: 0 Explanation: This ladder can be climbed without adding additional rungs.
Example 3:
Input: rungs = [3,4,6,7], dist = 2 Output: 1 Explanation: You currently cannot reach the first rung from the ground. Add a rung at height 1 to climb this ladder. The ladder will now have rungs at [1,3,4,6,7].
Constraints:
1 <= rungs.length <= 10^{5}
1 <= rungs[i] <= 10^{9}
1 <= dist <= 10^{9}
rungs
is strictly increasing.
Solutions
Solution 1: Greedy + Simulation
According to the problem description, we know that every time we plan to climb a new rung, we need to ensure that the height difference between the new rung and the current position does not exceed dist
. Otherwise, we need to greedily insert a new rung at a distance of $dist$ from the current position, climb a new rung, and the total number of rungs to be inserted is $\lfloor \frac{b  a  1}{dist} \rfloor$, where $a$ and $b$ are the current position and the height of the new rung, respectively. The answer is the sum of all inserted rungs.
The time complexity is $O(n)$, where $n$ is the length of rungs
. The space complexity is $O(1)$.

class Solution { public int addRungs(int[] rungs, int dist) { int ans = 0, prev = 0; for (int x : rungs) { ans += (x  prev  1) / dist; prev = x; } return ans; } }

class Solution { public: int addRungs(vector<int>& rungs, int dist) { int ans = 0, prev = 0; for (int& x : rungs) { ans += (x  prev  1) / dist; prev = x; } return ans; } };

class Solution: def addRungs(self, rungs: List[int], dist: int) > int: rungs = [0] + rungs return sum((b  a  1) // dist for a, b in pairwise(rungs))

func addRungs(rungs []int, dist int) (ans int) { prev := 0 for _, x := range rungs { ans += (x  prev  1) / dist prev = x } return }

function addRungs(rungs: number[], dist: number): number { let ans = 0; let prev = 0; for (const x of rungs) { ans += ((x  prev  1) / dist)  0; prev = x; } return ans; }

impl Solution { pub fn add_rungs(rungs: Vec<i32>, dist: i32) > i32 { let mut ans = 0; let mut prev = 0; for &x in rungs.iter() { ans += (x  prev  1) / dist; prev = x; } ans } }