What is an O(n) algorithm for finding bottom largest square?

Правка en2, от duckladydinh, 2021-01-30 21:47:19

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский duckladydinh 2021-01-30 21:47:19 2 Tiny change: 'i..i+x-1] <= x.\n\nTh' -> 'i..i+x-1] >= x.\n\nTh'
en1 Английский duckladydinh 2021-01-30 21:01:25 516 Initial revision (published)