84. Largest Rectangle in Histogram

Problem Link

Description

---

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

Solution

---

Python3

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        N = len(heights)
        lessFromLeft = [0] * N
        lessFromRight = [0] * N
        lessFromLeft[0] = -1
        lessFromRight[-1] = N
 
        for i in range(1, N):
            p = i - 1
 
            while p >= 0 and heights[p] >= heights[i]:
                p = lessFromLeft[p]
            
            lessFromLeft[i] = p
        
        for i in range(N - 2, -1, -1):
            p = i + 1
 
            while p < N and heights[p] >= heights[i]:
                p = lessFromRight[p]
            
            lessFromRight[i] = p
        
        res = 0
        for i in range(N):
            res = max(res, heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1))
        
        return res