84. Largest Rectangle in Histogram

Hard

Problem 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.

Examples

Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle has area = 10 (height = 5, width = 2).

Example 2:
Input: heights = [2,4]
Output: 4
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def largestRectangleArea(heights: List[int]) -> int:
    stack = []  # (index, height)
    max_area = 0
    
    # Add sentinel values
    heights = [0] + heights + [0]
    
    for i, height in enumerate(heights):
        start = i
        
        # Pop higher heights and calculate their areas
        while stack and stack[-1][1] > height:
            index, h = stack.pop()
            width = i - index
            max_area = max(max_area, width * h)
            start = index
        
        stack.append((start, height))
    
    return max_area

Java Solution


class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack stack = new Stack<>();
        int maxArea = 0;
        int[] h = new int[heights.length + 2];
        
        // Copy array with sentinel values
        System.arraycopy(heights, 0, h, 1, heights.length);
        
        for (int i = 0; i < h.length; i++) {
            while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
                int height = h[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

C++ Solution


class Solution {
public:
    int largestRectangleArea(vector& heights) {
        stack st;
        int maxArea = 0;
        
        // Add sentinel values
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                int height = heights[st.top()];
                st.pop();
                int width = i - st.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        
        return maxArea;
    }
};

JavaScript Solution


/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    const stack = [];  // [index, height]
    let maxArea = 0;
    
    // Add sentinel values
    heights = [0, ...heights, 0];
    
    for (let i = 0; i < heights.length; i++) {
        let start = i;
        
        while (stack.length && stack[stack.length - 1][1] > heights[i]) {
            const [index, height] = stack.pop();
            const width = i - index;
            maxArea = Math.max(maxArea, width * height);
            start = index;
        }
        
        stack.push([start, heights[i]]);
    }
    
    return maxArea;
};

C# Solution


public class Solution {
    public int LargestRectangleArea(int[] heights) {
        Stack stack = new Stack();
        int maxArea = 0;
        int[] h = new int[heights.Length + 2];
        
        // Copy array with sentinel values
        Array.Copy(heights, 0, h, 1, heights.Length);
        
        for (int i = 0; i < h.Length; i++) {
            while (stack.Count > 0 && h[stack.Peek()] > h[i]) {
                int height = h[stack.Pop()];
                int width = i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, height * width);
            }
            stack.Push(i);
        }
        
        return maxArea;
    }
}

Complexity Analysis

Solution Explanation

This solution uses a monotonic stack approach:

Key points: