Mountain Watching
InterviewTime limit1sMemory limit128 MB
Given a sequence of heights, find the longest consecutive block that rises (non-strictly) then falls (non-strictly), allowing a block that only rises or only falls.
- Level
Medium4 of 10
- Topics
- Array, Two pointers, Implementation, Greedy
- Solved
- No attempts yet
Problem
Bessie is gazing off toward the beautiful mountains in the distance and wonders: which one is the widest?
She takes height measurements one after another along the horizon, from left to right.
A mountain is a consecutive block of measurements whose heights first only rise (staying the same is allowed) and then only fall (staying the same is allowed). For example, is a mountain. A mountain on the edge of her field of view may only rise, or only fall.
The width of a mountain is the number of measurements it spans. Help Bessie find the widest mountain and report its width.
A typical horizon looks like this:
******* *
********* ***
********** *****
*********** ********* *
* ***************** *********** *** *
** ******************* ************* * * ******* *
**********************************************************************
?ddsssuussuussssssddddssddssssuuuuuuuuddddddssududssssuuudduddsssssuds
3211112333677777776543332111112344456765432111212111112343232111111211
aaaaa cccccccccccccccccccc eeeeeee ggggggggg
bbbbbbbbbbbbbbbbbbbbbbbbbbbb ddddd ffffffffff hhhhhhhhh
The mountains are labeled 'a', 'b', and so on; here mountain 'b' is the widest, with width 28.
Sometimes it is easiest to find a mountain's width once you know where its highest part is.
Constraints:
Input
- Line 1: a single integer .
- Lines 2 to : line contains a single integer .
Output
- A single line containing one integer: the width of the widest mountain.
Hint
Consider the measurements . The widest mountain is , so its width is . Other mountains include and . Note that is not a mountain, because it falls and then rises.