/**
* 84. 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:
* Input: [2,1,5,6,2,3]
* Output: 10
*/
See the below solutions to this problem on github.
I am explaining below the solution using stack as it is the most efficient solution. But the other solutions are also interesting.
Observation: Area is simply width * height. So if you can track for a given height span of width with items greater than that height then you can calculate the area efficiently. You can do this via a stack where you iterate the array of heights left to right while recording (adding) array indexes while height is increasing into a stack. And once height decreases you pop the indexes off the stack while calculating area.
Here is the algorithm:
- Add indexes to a stack while the height at indexes continues to increase. Stop adding indexes to the stack when the height at current index is less than the height at last index on top of stack or you reach the end of the array.
- When the above condition holds it is true by definition that the height for indexes between the index on top of stack and the index before current index are increasing.
- Calculate area based on the above
- Height is height of index on top of stack
- Width is i-index on top of stack -1 (-1 to exclude current index)
- While stack is not empty
- Take the height of index on top of stack and pop it from the stack
- The height calculated above by definition is the smallest height over the area one right of top of stack to the end of stack.
- Thus calculate area as height in A above * (length – index in b -1) “-1 to subtract the out the index in b”
Here is the code:
public int largestRectangleArea(int[] heights) {
this.heights = heights;
Stack<Integer> stack = new Stack<>();
stack.push(-1); //add sentinel
for (int i = 0; i < heights.length; i++) {
while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
//when the above condition is met , it means that the element on top of stack is higher than current
//index based on "heights[stack.peek()] > heights[i]"
//and by definition all elements between the current index on top of stack and i must be greater in height
//than the height on top of stack.
//so you get height via current stack index height
//and you get width by (i-1-index on top of stack). you subtract 1 from i to exclude current index
int h = heights[stack.pop()];
int priorIndex = stack.peek();
int width = i - priorIndex - 1; //subtract 1 to exclude current index (i)
int area = width * h;
maxArea = Math.max(area, maxArea);
}
stack.push(i);
}
while (stack.peek() != -1) {
int h = heights[stack.pop()];
//here any elements left on stack are greater than the last index
//so area is just there height * length - index (subtract 1 to remove index of element left on stack)
int width = heights.length - stack.peek() -1;
int area = h * width;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}