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
↵
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]
↵
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
