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.
Solution: max(the area of rectangle which height[i] is the shortest bar)
leftBound[i]: index of the first element less than height[i] starting from the left +1
rightBound[i]: index of the first element less than height[i] starting from the right -1
result = max(height[i]*(rightBound[i]-leftBound[i]))
注意：凡是求左边第一个比它小得数这类问题 用stack 存数组的index
策略是：
如果新来的数大于A[stack.peek()]， 直接push i to stack， otherwise stack.pop()直到找到第一个比他小得数停下，push i to stack.
这样对一个array来说 只要走一遍就知道每一个数的左边第一个比它小的数是哪个。
O(n) time.
Solution 1. Straightforward Version
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int[] leftBound = new int[height.length];
int[] rightBound = new int[height.length];
Stack<Integer> minStack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
leftBound[i] = 0;
} else {
leftBound[i] = minStack.peek() + 1;
}
minStack.push(i);
}
minStack = new Stack<>();
for (int i = height.length - 1; i >= 0; i--) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
rightBound[i] = height.length - 1;
} else {
rightBound[i] = minStack.peek() - 1;
}
minStack.push(i);
}
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
int area = height[i] * (rightBound[i] - leftBound[i] + 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
Solution 2. Fancy Version, One pass
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> minStack = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= height.length; i++) {
int curr = (i == height.length) ? -1 : height[i];
while (!minStack.isEmpty() && curr <= height[minStack.peek()]) {
int tmp = minStack.pop();
int left = minStack.isEmpty() ? 0 : minStack.peek() + 1;
int area = (i - left) * height[tmp];
maxArea = Math.max(area, maxArea);
}
minStack.push(i);
}
return maxArea;
}
