I'm just curious about the "stack" tag of this question.
For me the intuitive solution (and optimal) is the one has been posted several times.
(Search from left to right while maintaining the max height. O(n) time, O(1) space)
Does anyone know the solution using stack that might be better than the one above?