Largest Rectangle in Histogram
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.
Constraints:
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^5
Examples:
Input: [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 diagram.
Solutions
Stack-based approach
We use a stack to keep track of the indices of the histogram bars. We start by pushing the index of the first bar onto the stack. Then we iterate over the rest of the bars. If the current bar is smaller than the bar at the top of the stack, we calculate the area of the rectangle with the bar at the top of the stack as the smallest bar. We keep doing this until the stack is empty or the current bar is larger than the bar at the top of the stack. We then push the current index onto the stack. We repeat this process until we have processed all bars.
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int maxArea = 0;
for (int i = 0;
i <= heights.length;
i++) {
while (!stack.isEmpty() && (i == heights.length || heights[stack.peek()] > heights[i])) {
int h = heights[stack.pop()];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
return maxArea;
}Follow-up:
What if the histogram is not represented as an array of heights, but as a 2D array where each cell represents a bar in the histogram?
