LargestRectangleInHistogram.java

import java.util.Stack;

public class LargestRectangleInHistogram {
    static int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int n = heights.length;
        Stack<Integer> stack = new Stack<Integer>();
        int max_area = 0;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int top_height = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max_area = Math.max(max_area, w * top_height);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int top_height = heights[stack.pop()];
            int w = stack.isEmpty() ? n : n - stack.peek() - 1;
            max_area = Math.max(max_area, w * top_height);
        }
        return max_area;
    }

    public static void main(String[] args) {
        int[] nums0 = {6, 2, 5, 4, 5, 1, 6};
        System.out.println(largestRectangleArea(nums0));
        int[] nums1 = {6, 2, 5, 4, 5, 2, 6};
        System.out.println(largestRectangleArea(nums1));
    }
}