Largest Rectangle in Histogram — Monotonic Stack

Problem

Given heights of bars in a histogram, find the area of the largest rectangle.

Example: [2,1,5,6,2,3] → 10

Approach — Monotonic Increasing Stack

Maintain an increasing stack of bar indices. When we find a shorter bar:

Pop from stack
Height = heights[popped]
Width = current_index - stack.top - 1 (or current_index if stack is empty)

Add sentinel 0-height bar at end to flush stack.

Time: O(n) | Space: O(n)

Solutions

Python

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack=[-1]; max_area=0; heights=heights+[0]
        for i,h in enumerate(heights):
            while stack[-1]!=-1 and heights[stack[-1]]>=h:
                height=heights[stack.pop()]
                width=i-stack[-1]-1
                max_area=max(max_area,height*width)
            stack.append(i)
        return max_area

C++

class Solution {
public:
    int largestRectangleArea(vector<int>& h){
        h.push_back(0); stack<int> st; st.push(-1); int best=0;
        for(int i=0;i<h.size();i++){
            while(st.top()!=-1&&h[st.top()]>=h[i]){
                int ht=h[st.top()];st.pop();
                best=max(best,ht*(i-st.top()-1));
            }
            st.push(i);
        }
        return best;
    }
};

Java

class Solution {
    public int largestRectangleArea(int[] heights){
        Deque<Integer> st=new ArrayDeque<>(); st.push(-1);
        int[] h=Arrays.copyOf(heights,heights.length+1); int best=0;
        for(int i=0;i<h.length;i++){
            while(st.peek()!=-1&&h[st.peek()]>=h[i]){
                int ht=h[st.pop()]; best=Math.max(best,ht*(i-st.peek()-1));
            }
            st.push(i);
        }
        return best;
    }
}

Complexity

Time: O(n) | Space: O(n)

Key Takeaway

Stack holds indices. When popping, height = heights[popped], width = current - new_top - 1.