# AC Python code

• The first solution, search each height while finding the width.

``````class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
n = len(heights)
if n == 0:  return 0
max_rec = -1
left, right = [i for i in range(n)], [i for i in range(n)]    # left[i] is the most left 'index' making height[index]>=height[i]
# fill the list left (make use of previous results)
for i in range(n):
p = i
while p>=0 and heights[p]>=heights[i]:
if p != left[p]:    p = left[p]
else:   p -= 1
left[i] = p + 1
# fill the list right
for j in range(n-1, -1, -1):
p = j
while p<n and heights[p]>=heights[j]:
if p != right[p]:   p = right[p]
else:   p += 1
right[j] = p - 1
# scan heights and calculate max rectangle containing each elements
for k in range(n):
max_rec = max(heights[k]*(right[k]-left[k]+1), max_rec)
print(left, right)
return max_rec

``````

The second solution, using stack (insert a dummy 0 to the head of heights and push 0 index to stack).

``````class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
n = len(heights)
height, stack, h, max_area = [0]+heights, [0], 0, 0
for i in range(1, n+1):
while height[i] < height[stack[-1]]:
h = height[stack[-1]]
stack.pop()
w = i - stack[-1] - 1
max_area = max(w*h, max_area)
stack.append(i)
# in case stack is still not empty
r = stack[-1] + 1
while len(stack)>1:
h = height[stack[-1]]
stack.pop()
w = r - stack[-1] - 1
max_area = max(w*h, max_area)

return max_area
``````

Avoid treating not-empty stack by inserting another dummy 0 to the tail of heights.

``````class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
n = len(heights)
height, stack, h, max_area = [0]+heights+[0], [0], 0, 0
for i in range(1, n+2):
while height[i] < height[stack[-1]]:
h = height[stack[-1]]
stack.pop()
w = i - stack[-1] - 1
max_area = max(w*h, max_area)
stack.append(i)

return max_area
``````

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