Finding highest values in an array within a certain distance of each other

Question

I have an array of ints which represent altitudes, and I need to find out how many of those altitudes will be able to see the horizon to the west (the array is organized from west to east). The requirement for seeing the horizon is being higher than the last n/5 altitudes, where n is the length of the array.

This would be easy with two for loops, but I have to do it in O(n). So I can only iterate over the array once. I don't need a solution, just push in the right direction.

Answer 1

What about working backwards through the array? Start at the end and create a queue of every altitude you pass. If you see an altitude bigger than the current one, then none of the altitudes in the queue can see the horizon (so you can throw them out). If you get to n/5, then the last altitude in the queue can see the horizon (and obviously, you'll need to handle the case of more than n/5 elements in the queue).