84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example, Given heights = [2,1,5,6,2,3], return 10.

Solution: Stack

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        max_area = 0
        heights = [0] + heights + [0]

        # indices with increasing heights
        stack = [0]
        for idx, height in enumerate(heights):
            while height < heights[stack[-1]]:
                pre_height = heights[stack.pop()]
                area = pre_height * (idx - stack[-1] - 1)
                max_area = max(area, max_area)
            stack.append(idx)
        return max_area