LargestRectangle.java

packagecom.thealgorithms.stacks;

importjava.util.Stack;

/**
 *
 * @author mohd rameez github.com/rameez471
 */

publicfinalclassLargestRectangle {
privateLargestRectangle() {
 }

publicstaticStringlargestRectangleHistogram(int[] heights) {
intn = heights.length;
intmaxArea = 0;
Stack<int[]> st = newStack<>();
for (inti = 0; i < n; i++) {
intstart = i;
while (!st.isEmpty() && st.peek()[1] > heights[i]) {
int[] tmp = st.pop();
maxArea = Math.max(maxArea, tmp[1] * (i - tmp[0]));
start = tmp[0];
 }
st.push(newint[] {start, heights[i]});
 }
while (!st.isEmpty()) {
int[] tmp = st.pop();
maxArea = Math.max(maxArea, tmp[1] * (n - tmp[0]));
 }
returnInteger.toString(maxArea);
 }

publicstaticvoidmain(String[] args) {
assertlargestRectangleHistogram(newint[] {2, 1, 5, 6, 2, 3}).equals("10");
assertlargestRectangleHistogram(newint[] {2, 4}).equals("4");
 }
}