Frog on the Posts
Posts stand in a row and heights[i] is the height of post i. A frog only hops to the right, and its hops alternate:
- The 1st, 3rd, 5th, ... hop is an up hop: among the posts further right that are at least as high as its own post, it lands on the lowest one.
- The 2nd, 4th, 6th, ... hop is a down hop: among the posts further right that are at most as high as its own post, it lands on the highest one.
When several posts are equally good, the frog takes the nearest. When there is no such post, it is stuck. Return how many posts are good starts: posts from which the frog reaches the last post. The last post itself is a good start.
Example 1
Post 4 is the last post. From post 1 the up hop lands on the lowest higher post, which is the last one. From post 2 the frog hops up to post 3 and then down to post 4. Posts 0 and 3 have nothing high enough to their right.
Example 2
Each post has a post of equal height right after it, so every hop works.
Constraints
1 <= len(heights) <= 3000 <= heights[i] <= 10**5
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.