# Easy-to-understand 92ms Python solution, linear time and space.

• ``````class Solution(object):
# Helper function calculating how far each bar can be extended to the right.
def calmax(self, height):
stack = []
n = len(height)
rec = [0] * n
for i in xrange(len(height)):
while len(stack) > 0 and height[stack[-1]] > height[i]:
top = stack.pop()
rec[top] = i
stack.append(i)
for i in stack:
rec[i] = n
return rec
def largestRectangleArea(self, height):
# How far can each bar be extended to the right?
rec1 = self.calmax(height)
# How far can each bar be extended to the left?
rec2 = self.calmax(height[::-1])[::-1]
maxa = 0
n = len(height)
for i in xrange(n):
# Add the left and right part together
new = height[i] * (rec1[i] + rec2[i] - n)
maxa = max(new, maxa)
return maxa
``````

This solution can be made faster. But who cares if the complexity is still \Theta(n)?

• Hi, I am not sure how to calculate the time complexity when you are using stack in a loop. Can you explain why it is O(N)?

• Every element is pushed and popped exactly once.

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