84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Analysis

link: https://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Solution from Answer

public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    Deque<Integer> stack = new LinkedList<>();
    int result = 0;
    for (int i = 0; i <= heights.length; ++i) {
        int cur = i == heights.length ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peekLast()] >= cur) {
            int h = heights[stack.pollLast()];
            int left = stack.isEmpty() ? 0 : stack.peekLast() + 1;
            result = Math.max(result, h * (i - left));
        }
        stack.offerLast(i);
    }
    return result;
}