Gentle Trail Sections
Medium · monotonic deque
A hiker's logbook lists the altitude, in metres, at each checkpoint of a trail, in the order the checkpoints are passed. The list is heights.
A section is a run of checkpoints that follow each other with none skipped, so it is described by its first and last checkpoint. A section holding a single checkpoint is allowed. A section is gentle if the difference between its highest and its lowest altitude is at most limit.
Return how many gentle sections the trail has. Two sections are different when their first or last checkpoint differs, even if they list the same altitudes.
Examples
Example 1
Input: heights = [4, 2, 3, 7], limit = 1
Output: 5
The four single checkpoints are gentle, and so is the section 2, 3. The section 4, 2 has a difference of 2, and 3, 7 has a difference of 4.
Example 2
Input: heights = [5, 5, 5], limit = 0
Output: 6
Every section is flat. There are three of length 1, two of length 2 and one of length 3.
Constraints
- 1 <= len(heights) <= 10^5
- 0 <= heights[i] <= 10^9
- 0 <= limit <= 10^9