# Accepted O(n) Python solution using stack

• class Solution:
# @param height, a list of integer
# @return an integer
def largestRectangleArea(self, height):
#linearly scan the array, keep a stack
#if the stack is empty or cur > top of the stack, push cur to the stack
#else cur <= top of the stack, set cur as bar, pop item from the stack until top of the stack < cur
#for popped item, left index = index of its previous item in the stack, right index = index of bar
#tail case: for rest of the items in the array, set the top of the stack as bar
#           pop all the items, left index = index of its previous, right index = index of bar
if height == []: return 0
stack = []
result = 0
for i in range(0, len(height)):
if stack != [] and height[i] <= stack[-1][0]:
bar = height[i]
while stack != [] and stack[-1][0] >= bar:
cur = stack.pop()
if stack == []:
prev = -1   #no previous item, left index = -1
else:
prev = stack[-1][1]
result = max(result, cur[0]*( (i-1) -prev))
stack.append((height[i], i))

bar = stack[-1]
while stack != []:
cur = stack.pop()
if stack == []:
prev = -1   #no previous item, left index = -1
else:
prev = stack[-1][1]
result = max(result, cur[0]*(bar[1]-prev))
return result

• Tail case doesn't work well. Try height = [1, 2, 3, 4, 5].

• Inspired by yours. here's my version

# find the how many bars can extend to right
def extendBar(self, bar):
size = len(bar)
stack = [0]
extend = [0] * size
for i in xrange(1, size):
while len(stack) > 0 and bar[i] < bar[stack[-1]]:
top = stack.pop()
extend[top] = i - 1
stack.append(i)

while stack:
top = stack.pop()
extend[top] = size - 1

for i in xrange(size):
extend[i] = extend[i] - i

return extend

def largestRectangleArea(self, height):
size = len(height)
ans = 0
if size == 0:
return 0

extend_right = self.extendBar(height)
extend_left = self.extendBar(height[::-1])
extend_left = extend_left[::-1]

for i in xrange(size):
ans = max(ans, height[i] * (extend_right[i] + extend_left[i] + 1))

return ans

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