LargestRectangleInHistogram

gistfile1.java

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> st = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= height.length; i++) {
            int h = i == height.length ? 0 : height[i];
            if (st.isEmpty() || h >= height[st.peek()])
                st.push(i);
            else {
                int top = height[st.pop()];
                maxArea = Math.max(maxArea, top * (st.isEmpty() ? i : i - 1 - st.peek()));
                i--;
            }
        }
        return maxArea;
    }
}