package com.thealgorithms.datastructures.stacks;

import java.util.Stack;

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

public class LargestRectangle {

    public static String largestRectanglehistogram(int[] heights) {
        int n = heights.length, maxArea = 0;
        Stack<int[]> st = new Stack<>();
        for (int i = 0; i < n; i++) {
            int start = 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(new int[] { start, heights[i] });
        }
        while (!st.isEmpty()) {
            int[] tmp = st.pop();
            maxArea = Math.max(maxArea, tmp[1] * (n - tmp[0]));
        }
        return Integer.toString(maxArea);
    }

    public static void main(String[] args) {
        assert largestRectanglehistogram(new int[] { 2, 1, 5, 6, 2, 3 })
            .equals("10");
        assert largestRectanglehistogram(new int[] { 2, 4 }).equals("4");
    }
}