Largest Rectangle in Histogram

1package pkg5leetcode.top100;2 3/*4 * Largest Rectangle in Histogram | LC 845 * APPROACH: Monotonic stack finds width when popping lower bar.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class top100_LC84LargestRectangleInHistogram {11    static int largestRectangleArea(int[] heights) {12        Deque<Integer> st = new ArrayDeque<>();13        int best = 0;14        for (int i = 0; i <= heights.length; i++) {15            int h = i == heights.length ? 0 : heights[i];16            while (!st.isEmpty() && h < heights[st.peek()]) {17                int height = heights[st.pop()];18                int width = st.isEmpty() ? i : i - st.peek() - 1;19                best = Math.max(best, height * width);20            }21            st.push(i);22        }23        return best;24    }25 26    public static void main(String[] args) {27        check(largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}) == 10, "case1");28        check(largestRectangleArea(new int[]{2, 4}) == 4, "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}