Question
link
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.
For example,
Given height = [2,1,5,6,2,3],
return 10.
Stats
| Frequency |
2 |
| Difficulty |
5 |
| Adjusted Difficulty |
5 |
| Time to use |
---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is an extremely difficult question.
The idea of the solution (using stack) seems understandable, but can be very tricky when coding.
The basic idea is, always keep increasing elements in the stack. When I see a decrease in number, pop stack. And I calculate max area only when poping elements. In the end, a ‘0’ is inserted to the end, so that all stack item will be popped (and at the same time, max area been calculated).
Sorry if I did not explain well enough. Here is a better one:
We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.
1) Create an empty stack.
2) Start from first bar, and do following for every bar ‘hist[i]‘ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.
Time complexity of the stack solution is O(n). (Another algo analysis article here)
Solution
I wrote the code using idea from blog. It works, but there are 2 things that I got wrong.
First, if elements are equal. I shall also push it. I can not simply skip it, I don’t know why!
if (stack.isEmpty() || cur >= height[stack.peek()])
Second, about how to calculate the width of the rectangle. I used this before:
int width = stack.isEmpty() ? p : p - h;
It’s wrong, I must get the value of next element from stack, and then calculate width. Why? there might be element been popped before, which locate between these 2 elements in stack.
int width = stack.isEmpty() ? p : p - stack.peek() - 1;
Updated on July 4th, 2014: the above 2 points are very valid, especially the second. Keep in mind:
The values in stack means the last position that a height can be found. For example, height is (2, 10, 5) then the stack would have (2, removed, 5). When calculating the area for height 5, we should note the removed space is in consideration as well.
So, when equal height is found, pop it. Because you won’t need it any more. The stack only stores last position this height is found.
When stack is empty, the width of rectange should be calculated from 0.
Code
My code written on July 4th, 2014
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> stack = new Stack<Integer>();
stack.add(0);
int len = height.length;
int area = 0;
for (int i = 1; i <= len; i++) {
int h = i == len ? 0 : height[i];
// pop a element and calculate its max area
// pop until the top element is smaller than h, then push h
while (!stack.isEmpty() && h <= height[stack.peek()]) {
int pos = stack.pop();
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
area = Math.max(area, height[pos] * width);
}
stack.push(i);
}
return area;
}
My code written on July 18th, 2014
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<Integer>();
int p = 0;
while (p < height.length) {
if (stack.isEmpty() || height[stack.peek()] <= height[p]) {
stack.push(p);
p++;
} else {
int h = stack.pop();
int w = stack.isEmpty() ? p : p - stack.peek() - 1;
int area = height[h] * w;
maxArea = Math.max(maxArea, area);
}
}
while (!stack.isEmpty()) {
int h = stack.pop();
int w = stack.isEmpty() ? p : p - stack.peek() -1;
int area = height[h] * w;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}