1936. Add Minimum Number of Rungs Medium

1/**
2 * [1936] Add Minimum Number of Rungs
3 *
4 * 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.
5 * 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.
6 * Return the minimum number of rungs that must be added to the ladder in order for you to climb to the last rung.
7 *  
8 * Example 1:
9 * 
10 * Input: rungs = [1,3,5,10], dist = 2
11 * Output: 2
12 * Explanation:
13 * You currently cannot reach the last rung.
14 * Add rungs at heights 7 and 8 to climb this ladder. 
15 * The ladder will now have rungs at [1,3,5,<u>7</u>,<u>8</u>,10].
16 * 
17 * Example 2:
18 * 
19 * Input: rungs = [3,6,8,10], dist = 3
20 * Output: 0
21 * Explanation:
22 * This ladder can be climbed without adding additional rungs.
23 * 
24 * Example 3:
25 * 
26 * Input: rungs = [3,4,6,7], dist = 2
27 * Output: 1
28 * Explanation:
29 * You currently cannot reach the first rung from the ground.
30 * Add a rung at height 1 to climb this ladder.
31 * The ladder will now have rungs at [<u>1</u>,3,4,6,7].
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	1 <= rungs.length <= 10^5
37 * 	1 <= rungs[i] <= 10^9
38 * 	1 <= dist <= 10^9
39 * 	rungs is strictly increasing.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/add-minimum-number-of-rungs/
45// discuss: https://leetcode.com/problems/add-minimum-number-of-rungs/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn add_rungs(rungs: Vec<i32>, dist: i32) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_1936() {
63    }
64}
65