Given heights array representing histogram bars, find area of largest rectangle.
Input: heights=[2,1,5,6,2,3] → Output: 10
Input: heights=[2,4] → Output: 4
Monotonic stack: maintain increasing stack. When height decreases, calculate area with popped bar as smallest.
- Use stack (storing indices)
- For each bar: while stack top height > current, pop
- Width = current_index - stack_top_index - 1
- Area = popped_height * width; track max
- Process remaining stack after loop
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int max = 0, n = heights.length;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
max = Math.max(max, height * width);
}
stack.push(i);
}
return max;
}
- Time Complexity: O(n)
- Space Complexity: O(n)