Hard

Largest Rectangle in Histogram

098

Given bar heights, return the largest rectangle area in the histogram.

EXAMPLES

Example 1

Input
{
  "heights": [
    2,
    1,
    5,
    6,
    2,
    3
  ]
}

Output
10

FUNCTION SHAPE

heights: intArray→int

SOLUTION NOTE

The maximal rectangle must fully include some bar. Height is the bar, width is determined by PL and NL. Formula: max(heights[i] * (nl[i] - pl[i] - 1))

Reveal reference solution +

pythonREFERENCE

def largestRectangleArea(self, heights: List[int]) -> int:
    def nl(A):
        n = len(A)
        stack = []
        res = [n] * n
        for i in range(n):
            while stack and A[stack[-1]] > A[i]:
                res[stack[-1]] = i
                stack.pop()
            stack.append(i)
        return res

    def pl(A):
        n = len(A)
        stack = []
        res = [-1] * n
        for i in range(n-1, -1, -1):
            while stack and A[stack[-1]] > A[i]:
                res[stack.pop()] = i
            stack.append(i)
        return res

    NL = nl(heights)
    PL = pl(heights)
    return max(heights[i] * (NL[i] - PL[i] - 1) for i in range(len(heights)))

TimeO(n)

SpaceO(n)

Open on LeetCode ↗