Maximum area of rectangle in histogram – why do we need stacks?
Consider the following problem (and solution):
Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram.
The key idea is to calculate:
R[i] = Area of the largest rectangle with the bar at i is as the
smallest bar in the rectangle (i.e. width = H[i]) left[i] = the left
most boundary of R[i], which is the leftmost bar greater than H[i].
right[i] = the right most boundary of R[i], which is the rightmost bar
greater than H[i].
I know a stack
is needed to compute right
and left
, but I think I can provide a similar solution without using a stack :
def max_area_rect(lst):
n = len(lst)
right = [-1] * n
left = [-1] * n
right[n - 1] = n
for i in range(n - 2, -1, -1):
right[i] = i + 1 if lst[i] > lst[i + 1] else right[i + 1]
left[0] = -1
for i in range(1, n):
left[i] = i - 1 if lst[i - 1] < lst[i] else left[i - 1]
max_res = -1
for i in range(n):
right_len = right[i] - i -1
left_len = i - left[i] + 1
h = min(lst[right_len - 1], lst[left_len + 1])
res = (right_len + left_len) * h
if res > max_res:
max_res = res
return max_res
# test
print(max_area_rect([4, 2, 1, 8, 6, 8, 5, 2])) # expected result: 20
So my question is: why do we need stacks? Does my method work?
Solution
The definition of left[i]
you mentioned
left[i] = the left most boundary of R[i], which is the leftmost bar greater than H[i]
What you defined in the code
left[i] = i - 1 if lst[i - 1] < lst[i] else left[i - 1]
That is, if the bar on the left is higher, it means that you placed left[i] = left[i-1].
However, the error here is that left[i-1] stores something greater than lst[i-1]
instead of lst[i].
For example, in the sequence 6, 8, 5 you enter, left[i]8 should not contain 6, so left[i] should
be i but left[
i
]
5 should include 6
and 8
That’s what your code ignores.