# Python solution without using stack. (with explanation)

• The algorithm using stack actually is not quite intuitive. At least I won't think about using it at first time.

It is more natural to think about this way. Let left[i] to indicate how many bars to the left (including the bar at index i) are equal or higher than bar[i], right[i] is that to the right of bar[i], so the the square of the max rectangle containing bar[i] is simply height[i] * (left[i] + right[i] - 1)

``````class Solution:
# @param height, a list of integer
# @return an integer
def largestRectangleArea(self, height):
n = len(height)

# left[i], right[i] represent how many bars are >= than the current bar

left = [1] * n
right = [1] * n
max_rect = 0

# calculate left
for i in range(0, n):
j = i - 1
while j >= 0:
if height[j] >= height[i]:
left[i] += left[j]
j -= left[j]
else: break

# calculate right
for i in range(n - 1, -1, -1):
j = i + 1
while j < n:
if height[j] >= height[i]:
right[i] += right[j]
j += right[j]
else: break

for i in range(0, n):
max_rect = max(max_rect, height[i] * (left[i] + right[i] - 1))

return max_rect
``````

Note, this algorithm runs O(n) not O(n^2)! The while loop in the for loop jumps forward or backward by the steps already calculated.

• This is definitely a more intuitive way than the stack. Especially the jump forward idea!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.