Here's the solution:
function largestRectangleArea(heights)
n := length of heights
stack := empty stack // stores indices
maxArea := 0
for i from 0 to n - 1
while stack is not empty and heights[i] < heights[top of stack]
j := pop from stack
if stack is empty
left := -1
else
left := top of stack
width := i - left - 1
area := heights[j] × width
maxArea := max(maxArea, area)
push i onto stack
// Pop remaining bars
while stack is not empty
j := pop from stack
if stack is empty
left := -1
else
left := top of stack
width := n - left - 1
area := heights[j] × width
maxArea := max(maxArea, area)
return maxArea
Time: . Space: .