Hi,

Recently I came across a problem like this:

Given h[1..n] where h[i] denotes the height of column i, find the largest x such that there exists some i where h[i..i+x-1] <= x.

The best I could think of is O(nlogn): binary search for the value of x and do a linear check. However, this problem reminds me of finding the largest rectangle which could be done in O(n). So I wonder if there also exists a linear solution to this problem?

Thanks