837. Close-Step Climb
A mountain guide lists the altitudes of a sequence of campsites in the order they appear along a ridge, stored in nums. A trekker may skip campsites, but the campsites actually visited must keep getting strictly higher, and each visit may climb by at most k metres compared with the previous visited one.
Return the maximum number of campsites the trekker can visit. A single campsite always counts as a valid visit, so the answer is at least 1. Equal altitudes are not allowed back to back because the climb must be strictly positive.
Aim for time O(n log M) where M is the largest altitude, and space O(M).
Example 1
- Input:
- nums = [12,3,9,14,10,17,11,20], k = 4
- Output:
- 4
- Explanation:
The chain 12, 14, 17, 20 grows by 2, 3 and 3, all within the allowed step of 4, and no chain of five exists.
Example 2
- Input:
- nums = [30,10,20,40,25,35,50], k = 15
- Output:
- 5
- Explanation:
Picking 10, 20, 25, 35, 50 uses steps 10, 5, 10 and 15, so five photos can be kept.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i] ≤ 105
1 ≤ k ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log M)
- Space
- O(M)