84. Largest Rectangle in Histogram

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: heights = [2,1,5,6,2,3] Output: 10

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

Solution Approach

The solution approach involves using a monotonic stack to keep track of indices of histogram bars, allowing for efficient calculation of the largest rectangle by determining the nearest smaller bars on both sides for each bar.

Algorithm

1. Monotonic Stack Construction: Use a monotonic stack to track the indices of the histogram bars in increasing order, which helps identify the nearest smaller bars on both the left and right sides for each bar.
2. Boundary Arrays: Create two arrays, left and right, to store the indices of the nearest smaller bars to the left and right of each bar respectively, using the stack to populate these arrays efficiently.
3. Area Calculation: Calculate the area of the rectangle for each bar by using the width derived from the left and right boundaries and update the maximum area found.

Implement

    class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left, right = [0] * n, [n] * n

        mono_stack = []
        for i in range(n):
            while mono_stack and heights[mono_stack[-1]] >= heights[i]:
                right[mono_stack[-1]] = i
                mono_stack.pop()
            left[i] = mono_stack[-1] if mono_stack else -1
            mono_stack.append(i)
        
        max_area = 0   
        for i in range(n):
            current_area = (right[i] - left[i] - 1) * heights[i]
            max_area = max(max_area, current_area)
        
        return max_area

    
    

Twitter  facebook  Email