# Largest Rectangle in Histogram

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]))

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;
}```
Share