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
class Solution {
public int largestRectangleArea(int[] h) {
int n = h.length;
Stack<Integer> st = new Stack<>();
int[] left = new int[n];
int[] right = new int[n];
// finding closest smaller element on left
for (int i = 0; i < n; i++) {
while (st.size() != 0 && h[st.peek()] >= h[i]) {
st.pop();
}
if (st.size() == 0)
left[i] = -1;
else
left[i] = st.peek();
st.push(i);
}
st.clear();
// finding closest smaller element on right
for (int i = n - 1; i >= 0; i--) {
while (st.size() != 0 && h[st.peek()] >= h[i]) {
st.pop();
}
if (st.size() == 0)
right[i] = n;
else
right[i] = st.peek();
st.push(i);
}
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, h[i] * (right[i] - left[i] - 1));
}
return max;
}
}
Last updated