Largest Rectangle in Histogram
LintCode-122.Largest Rectangle in Histogram
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
Given height = [2,1,5,6,2,3],
return 10.
public class Solution {
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> stack = new Stack<>();
int max = 0;
int i = 0;
while (i < height.length) {
if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
stack.push(i);
i++;
} else {
int h = height[stack.pop()];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
max = Math.max(max, h * w);
}
}
while (!stack.isEmpty()) {
int h = height[stack.pop()];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
max = Math.max(max, h * w);
}
return max;
}
}
Hope this helps,
Michael