This problem can be solved using**Monotonic Stack**.

* The`heights` in the stack from bottom to top are in ascending order.

* While`current_height < stack_top_height`, pop`stack_top_height`.

* Follow**Monotonic Stack**'s common rule:**only calculating when`pop()` is happening**. This common rule can be applied to calculating result for**most** of the`Monotonic Stack` problems.

*Disappeared heights (popped by`current_height` or popped by`stack_top_height`)areall taller than`stack_top_height`. This logic will be used to calculate the`width`.

*To calculate the`width`, therearetwo ways:

Detailed solutions will be given later, and now only the best practices in 7 languages are given.

* The last`popped_index` from stack should be kept since we need it to calculate the`width`.

* Disappeared heights (popped when`current_height < stack_top_height`) are all taller than`stack_top_height`. This logic will be used to calculate the`width`.

* Time:`O(n)`.

* Space:`O(n)`.

classSolution:

deflargestRectangleArea(self,heights: List[int]) ->int:

max_area=0

index_stack= []

heights.append(0)# different from way 2

for i, heightinenumerate(heights):

popped_index=None# different from way 2

while index_stackand height< heights[index_stack[-1]]:

popped_index= index_stack.pop()

area= heights[popped_index]* (i- popped_index)# different from way 2

max_area=max(max_area, area)

if popped_indexisnotNone:# different from way 2

i= popped_index

heights[i]= height

index_stack.append(i)

return max_area

classSolution:

deflargestRectangleArea(self,heights: List[int]) ->int:

heights= [0]+ heights+ [0]

max_area=0

index_stack= []

heights= [0]+ heights+ [0]# different from way 1

for i, heightinenumerate(heights):

while index_stackand height< heights[index_stack[-1]]:

popped_index= index_stack.pop()

popped_height= heights[popped_index]

left_index= index_stack[-1]# popped_height's remaining left heights are all shorter than 'popped_height', because when 'popped_height' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.

right_index= i# popped_height's right heights (which are all taller than 'popped_height') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.

width= right_index- left_index-1# So in the range of 'width', they are all no shorter than `popped_height`, although they have been popped out of the stack (disappeared).

left_index= index_stack[-1]#Different from way 1.popped_height's remaining left heights are all shorter than 'popped_height', because when 'popped_height' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.

right_index= i#Different from way 1.popped_height's right heights (which are all taller than 'popped_height') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.

width= right_index- left_index-1#Different from way 1.So in the range of 'width', they are all no shorter than `popped_height`, although they have been popped out of the stack (disappeared).

area= popped_height* width

if area> max_area: