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 <= 105
1 <= rungs[i] <= 109
1 <= dist <= 109
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)$.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|