Question

Code

• Memorise the current height, and which index can the current height be extended to
• pop from the stack if the last column in higher than current

class Solution(object):
    def largestRectangleArea(self, heights):
        stack = []
        maxH = 0

        for i, h in enumerate(heights):
            start = i
			# The current tail of stack cannot be extended further, since the new h is smaller than it
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxH = max(maxH, height * (i - index))
                start = index
            stack.append((start, h))

		# All heights than can extend to the end
        for i, h in stack:
            maxH = max(maxH, (len(heights) - i) * h)


        return maxH