Hint: the trick for reaching time
O(N)
complexity is building and updating a list of tuples (position, height) representing the
meaningful buildings to the left of the current one.
Where
meaningful buildings means buildings occurring in decreasing height order.
For instance, when your code processes the fourth building
relev. |
v v V
height = [140,160,140,110,90,120,160,140,110]
the list of
meaningful buildings should be
[(2,160),(3,140)]