Largest Rectangle in Histogram
Created: February 25, 2019 by [lek-tin]
Last updated: February 25, 2019
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:
Input: [2,1,5,6,2,3]
Output: 10
Solution:
Push height into the stack in ascending order. When we encounter a height that is shorter than te top of the stack, we start to calculate area by popping heights out of the stack.
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) return 0;
Stack<Integer> stack = new Stack<Integer>();
int maxArea = 0;
for (int i = 0; i <= heights.length; i++) {
int h = i == heights.length ? 0 : heights[i];
while (!stack.isEmpty() && h < heights[stack.peek()]) {
int height = heights[stack.pop()];
int start = stack.isEmpty() ? -1 : stack.peek();
int area = height * (i - start - 1);
maxArea = Math.max(maxArea, area);
}
stack.push(i);
}
return maxArea;
}
}